9400232 Preparata Recent research on parallel computation has focused primarily on algorithmic design, and, more specifically, on the elucidation of the inherent parallelism of a wide variety of problems. This approach has frequently de-emphasized the communication aspect of parallel computation, and has placed no bound on the number of deployed processors (granularity). As parallel computing systems appear on the market, a more global view than the identification of parallelism is called for. To contribute to this emerging outlook, the following research topics are addressed in this project: (1) Since it appears that the more plausible parallel systems of the near future are coarse-grained, (i.e., interconnections of moderate number of large, powerful microprocessors), algorithms for this model must be systematically developed to gain insight into general paradigms (routing), and general communication primitives are to be studied, for incorporation into the run-time system; (2) As devices become smaller and faster, physical limitations become increasingly relevant. In a limiting technology, mesh-like architecture's are the only scalable ones. On such networks, it is important to devise practicable shared-memory emulation schemes (the P-RAM assumes an increasing role as a programming model) to evaluate the effect of memory granularity and hierarchy, and to investigate the structure and functionality of the most suitable most modules. (3) Locality has been long recognized as an important source of efficiency in parallel computing. An intriguing relation between locality and area-time theories of VLSI deserves careful scrutiny, since exploitation of locality and emulation (of an architecture by another) appear to be the key to program portability. ***
