ACM SIGARCH Computer Architecture News · 1990 · 17 citations · 17 references
ComputingComputer EngineeringComputer ScienceCompilersParallel AlgorithmsParallel ComputingData ParallelismData SynchronizationParallel Algorithm DesignParallel Computing SystemsSynchronization PrimitivesCompile-time OptimizationCompiler DesignData AccessLoop ParallelizationMultiprocessor SynchronizationNested StructureSynchronizationSynchronization Mechanisms
The major source of parallelism in ordinary programs is do loops. When loop iterations of parallelized loops are executed on multiprocessors, the cross-iteration data dependencies need to be enforced by synchronization between processors. Existing data synchronization schemes are either too simple to handle general nested loop structures with non-trivia array subscript functions or inefficient due to the large run-time overhead. In this paper, we propose a new synchronization scheme based on two data-oriented synchronization instructions: synch_read(x,s) and synch_write(x,s). We present the algorithm to compute the ordering number, s, for each data access. Using our scheme, a parallelizing compiler can parallelize a general nested loop structure with complicated cross-iteration data dependencies. If the computations of ordering numbers cannot be done at compile time, the run-time overhead is smaller than the other existing run-time schemes.
17
The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer
Gottlieb, Grishman, Kruskal et al. · IEEE Transactions on Computers · 1983 · 746 citations
Conversion of control dependence to data dependence
John R. Allen, Ken Kennedy, Carrie Porterfield et al. · 1983 · 605 citations