It is well known that parallel processing in general, and shared memory multiprocessing in particular, offers a promising future to achieve high computational speeds. A number of researchers have recognized, however, that as the number of processing elements (PEs) in the multiprocessor increase, the communication and synchronization overheads required among subtasks of a parallel algorithm can reduce the speedup, and, consequently, defeat the very purpose of parallel processing. They argue that for effective parallel algorithm analysis, communication and synchronization complexity measures should be used as performance criteria in addition to the usual parallel time complexity measure. As a first step to support this argument, they have developed communication and synchronization measures for parallel algorithms. A parallel algorithm on a shared memory multiprocessor is modeled by a directed acyclic graph (DAG) with vertices corresponding to computed values and edges to dependencies. The DAGs of many practical numerical algorithms result in regular structures which are suitable to graph- theoretic and combinatorial analyses. They have used the communication measure to prove a trade-off result between computation time and communication for a triangular solver algorithm. With this trade-off result, they can precisely capture the intuitive notion of, "communication increases as the computation time decreases." In the proposed project, they wish to continue the research in several ways as detailed in the project description. They can succinctly state an important goal: given an algorithm, they should be able to state the time, communication, and synchronization requirements, and any resulting trade-offs as a function of the size of the problem, the number of PEs, and the architecture.
