Evaluation of Multithreaded Architectures
Multithreading (MT) programming and execution models have an increasing impact on computer technology. This trend is driven by the need to increase processor utilization and deal with the memory-processor speed gap. The underlying rationale to increase processor utilization is a varying mix of new metrics that take performance improvements as well as better power and cost budgeting into account. Yet, it remains a challenge to identify and productively program applications for these architectures with a resulting substantial performance improvement. ;PNNL has been pursuing multiple efforts to investigate how multithreaded architectures and execution models can benefit scientific applications.
Architectures
The main focus has been on Cray and Sun systems. In addition to work on the Cray MTA-2, we have been targeting two architectures available in the PNNL's Advanced Computing Technology (ACTL) laboratory: a Sun T1 server equipped with the Niagara processor and the first ever Cray XMT machine;shipped by Cray.
Application Studies
Biology
BioGraphE is a framework for connecting graph problems in biology to computational solvers and high-performance systems. This framework enables computational biologists to identify and bring in graph analysis applications and to easily connect them to efficient and powerful computational software and hardware that are specifically designed and tuned to solve complex graph problems. We are investigating a Boolean satisfiability solver known as Survey Propagation to serve as the initial core computational solver. We are developing high-performance parallel implementations of the Boolean satisfiability solver on multi-threaded processor architectures including the Cray XMT.
Power Systems
The static State Estimation problem on a power grid is a critical application for power grid control and operations. The problem consists of given topological information of the grid, line flows, partial voltage or injection information from the nodes, compute a reliable estimate of the system state, which includes voltages at all nodes of the grid, as well as validating the structure of the model and the parameter values. The estimation involves solving a non-linear Weighted Least Squares (WLS) problem using a Newton-Raphson iterative approach. The topological structure of the power grid being analyzed induces a sparse matrix representation of the problem, which can be solved using sparse solvers. We ported and fully parallelized a sequential Fortran version of the WLS power state estimation problem to the Cray MTA-2 achieving greater speedups and greater scalability than what's possible on traditional cache-based non-multithreaded architectures.
Cybersecurity
Analysis performed on network traffic packet headers can be used to detect anomalies, in order to locate and characterize network attacks and help predict and mitigate future attacks. We have used a widely applicable method from conditional probablity to detect anomalies in categorical data. This method focuses on analyzing combinations of variables and instantiations of values for those variables in multivariate categorical data. We use a fine-grained multithreaded parallel algorithm to keep track of variables, their value instances and "interesting" combinations thereof by representing the data set as a n-ary tree, in which nodes can be updated and inserted in parallel. Our implementation on the Cray MTA-2 exhibits linear speedups for large data sets in spite of requiring a fine-grained locking protocol to control simultaneous updates on the nodes.
Outreach
MTAAP is a new series of IPDPS workshops with focus on multithreaded architectures and applications was initiated in 2007.
Related Papers
Chad Scherrer, Nathaniel Beagley, Jarek Nieplocha, Andres Marquez, John Feo, and Daniel Chavarria,;Probability Convergence in a Multithreaded Counting Application, Proc. IPDPS/MTAAP'07 Workshop. 2007.
Jarek Nieplocha,Andrès Márquez, John Feo, Daniel G. Chavarría-Miranda, George Chin Jr., Chad Scherrer, Nathaniel Beagley: Evaluating the potential of multithreaded platforms for irregular scientific computations. Conf. Computing Frontiers 2007: 47-58.
George Chin Jr., Daniel G., Grant C. Nakamura, and Heidi J. Sofia: A High-Performance Computational Framework for Bionetwork Analysis, Proceedings of the 2007 Symposium of Computations in Bioinformatics and Bioscience.
George Chin Jr., Grant C. Nakamura, Daniel G. Chavarria, and Heidi J. Sofia: Graph Mining of Networks from Genome Biology, Proceedings of the 2007 IEEE Conference on Bioinformatics and Bioengineering.