One type of interconnection network for a medium to large-scale parallel processing system (i.e., a system with 2/sup 6/ to 2/sup 16/ processors) is a buffered packet-switched multistage interconnection network (MIN). It has been shown that the performance of these networks is satisfactory for uniform network traffic. More recently, several studies have indicated that the performance of MIN's is degraded significantly when there is hot spot traffic, that is, a large fraction of the messages are routed to one particular destination. A multipath MIN is a MIN with two or more paths between all source and destination pairs. This research investigates how the Extra Stage Cube multipath MIN can reduce the detrimental effects of tree saturation caused by hot spots. Simulation is used to evaluate the performance of the proposed approaches. The objective of this evaluation is to show that, under certain conditions, the performance of the network with the usual routing scheme is severely degraded by the presence of hot spots. With the proposed approaches, although the delay time of hot spot traffic may be increased, the performance of the background traffic, which constitutes the majority of the network traffic, can be significantly improved.>

A mixed-mode parallel machine's processing elements are capable of operating in and switching between the SIMD and MIMD modes of parallelism. This paper analyzes various mappings of image correlation algorithms onto a mixed-mode parallel processing system. The trade-offs that exist between the SIMD and MIMD modes are the primary basis employed in comparing different mappings of a parallel algorithm onto a mixed-mode system. The scalability of the image correlation algorithms discussed here is shown to be impacted by the mode of parallelism used. The analytical results are supported by experiments on the PASM prototype.

Parallel implementations of the computationally intensive task of solving multiple quadratic forms (MQFs) have been examined. Coupled and uncoupled parallel methods are investigated, where coupling relates to the degree of interaction among the processors. Also, the impact of partitioning a large MQF problem into smaller non-interacting subtasks is studied. Trade-offs among the implementations fo various data-size/machine-size ratios are categorized in terms of complex arithmetic operation counts, communicatino overhead, and memory storage requirements.

One type of interconnection network for a medium to large-scale parallel processing system (i.e., a system with 26 to 216 processors) is a buffered packet-switched multistage interconnection network (MIN). It has been shown that the per formance of these networks is satisfactory for uniform network traffic. More recently, several studies have indicated that the performance of MINs is degraded significantly when there is hot spot traffic, that is, a large fraction of the messages are routed to one particular destination. A multipath MIN is a MIN with two or more paths between all source and destination pairs. This research investigates how the Extra Stage Cube multipath MIN can reduce the detrimental effects of tree satura tion caused by hot spots. Simulation is used to evaluate the per formance of the proposed approach. The objective of this evaluation is to show that, under certain conditions, the perfor mance of the network with the usual routing scheme is severely degraded by the presence of hot spots. With the proposed approach, although the delay time of hot spot traffic may be increased, the performance of the background traffic, which constitutes the majority of the network traffic, can be significantly improved.

Features of an explicitly parallel programming language targeted for reconfigurable parallel processing systems, where the machine's N processing elements (PEs) are capable of operating in both the SIMD and SPMD modes of parallelism, are described. The SPMD (single program-multiple data) mode of parallelism is a subset of the MIMD mode where all processors execute the same program. By providing all aspects of the language with an SIMD mode version and an SPMD mode version that are syntactically and semantically equivalent, the language facilitates experimentation with and exploitation of hybrid SIMD/SPMD machines. Language constructs (and their implementations) for data management, data-dependent control-flow, and PE-address-dependent control-flow are presented. These constructs are based on experience gained from programming a parallel machine prototype and are being incorporated into a compiler under development. Much of the research presented is applicable to general SIMD machines and MIMD machines.>

Language constructs (and their implementations) for execution mode management and achieving the overlap of control unit and processor operations in an explicitly parallel programming language are described. These are targeted to reconfigurable parallel processing systems, where the machine's processors are capable of operating in both the single-instruction-multiple data (SIMD) and single program-multiple data (SPMD) modes of parallelism. The SPMD mode of parallelism is a subset of the multiple instruction-multiple data (MIMD) mode where all processors execute the same program. By providing all aspects of the language with an SIMD and an SPMD version that are syntactically and semantically equivalent, the language facilitates experimentation with and exploitation of hybrid SIMD/SPMD machines.>

Efficient data layout is an important aspect of the compilation process. A model for the creation of perfect memory maps for large-scale parallel machines capable of user-controlled partitionable single-instruction-multiple data/single-program-multiple data (SIMD/SPMD) operation is developed. The term perfect implies that no memory fragmentation occurs and ensures that the memory map size is kept to a minimum. A major constraint on solving this problem is based on the single program nature of both the SIMD and SPMD modes of parallelism. It is assumed that all processors within the same submachine used identical addresses to access corresponding data items in each of their local memories. Necessary and sufficient conditions are derived for being able to create perfect memory maps, and results are applied to several partitionable interconnection networks.>