A processor self-scheduling scheme is proposed for general parallel nested loops in multiprocessor systems. In this scheme, programs are instrumented to allow processors to schedule loop iterations among themselves dynamically at run time without involving the operating system. The scheme has two levels. At the low level, it uses simple fetch-and-op operations to take advantage of the regular structure in the innermost parallel loop nests; at the high level, the irregular structure of the outer loops (parallel or serial) and the IF-THEN-ELSE constructs are handled by using dynamic parallel linked lists. The larger granularity or the processes at the high level easily justifies the added overhead incurred from maintaining such dynamic data structures. The use of guided self-scheduling (GSS) and shortest-delay self-scheduling (SDSS) in this scheme is analyzed.>

An effective dynamic processor self-scheduling scheme is presented for general parallel program constructs in a restructuring compiler. In the program constructs, parallel loops, serial loops, if-then-else constructs and a generalization of fork-joins can be nested in an arbitrary order, and procedure calls can be involved in any level of the nested constructs. In parallel programs, a piece of the program code, such as loop iterations, is called a chore, which is considered to be a work unit in the program. In this scheme, processors schedule themselves to the chores dynamically at execution time without involving the operating system. Memory management is another issue addressed. Efficiency concerns dictate treating chore locality differently from procedure locality. As a corollary, the number of call frames required at any one time for a nonrecursive procedure is bounded by the number of processors.>

Several parallel convolution algorithms for array processors with N/sup 2/ processing elements (PEs) connected by mesh, hypercube, and shuffle-exchange topologies, respectively, are presented. The computation time complexity is the same for array processors with different interconnection networks. The communication time complexity, however, varies from network to network, and is the main focus. It is shown that by using inter-PE communication networks efficiently, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the overall time complexity (including computation and communication) of algorithms is reduced to O(M/sup 2/).>

In this paper a new language operator, a generalized morphic replication, is introduced. Let Ω be a finite set of morphisms and reversal morphisms from ∑* into Δ*, and ω be in Ω*. A morphic replicator is defined as follows: for each x in ∑* define ω(x) to be h1(x) … hm(x), where |ω| = m and ω = h1 … hm. A generalized morphic replication extends ω to languages by ω(L) = {ω(x): x is in L} and to sets W of morphic replicators, where W ⊆ Ω*, W(x) = {ω(x): ω is in W} and W(L) = UW(x), where the union is taken over all x in L. It is shown that the class of languages accepted in real time by a non-deterministic reversal-bounded multitape Turing machine, the class of NP, and the class of the recursively enumerable sets, are all closed under the generalized morphic replication when the morphisms and the reversal morphisms are, respectively, linear-erasing, polynomial-erasing, and arbitrary.

This correspondence presents several parallel algorithms for image template matching on an SIMD array processor with a hypercube interconnection network. For an N by N image and an M by M window, the time complexity is reduced from O(N2M2) for the serial algorithm to O(M2/K2 + M * log2 N/K + log2 N * log2 K) for the N2K2-PE system (1 ¿ K ¿ M), or to O(N2M2/L2) for the L2-PE system (L ¿ N). With efficient use of the inter-PE communication network, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the time complexity is greatly reduced.