Efficient task migration is an important feature in parallel and distributed programs, in particular to support checkpointing and recovery for fault tolerance. It is also very useful in distributed environments like networks of workstations where external loads are often unpredictable and dynamic in nature. We propose simple language extensions (ELMO) to existing sequential programming languages like C, Fortran or C++, that provide an object based task parallel execution model. Tasks may be dynamically created, are location transparent, and may be migrated or check pointed transparently by the system. ELMO's language features, together with the requisite compiler support is presented.

Simulated annealing, a methodology for solving combinatorial optimization problems, is a very computationally expensive algorithm and, as such, numerous researchers have undertaken efforts to parallelize it. In this paper, we investigate three of these parallel simulated annealing strategies when applied to standard cell placement, specifically the TimberWolfSC placement tool. We have examined a parallel moves strategy, as well as two new approaches to parallel cell placement-multiple Markov chains and speculative computation. These algorithms have been implemented in ProperPLACE, our parallel cell placement application, as part of the ProperCAD II project. We have constructed ProperPLACE so that it is portable across a wide range of parallel architectures. Our parallel moves algorithm uses novel approaches to dynamic message sizing, message prioritization, and error control. We show that parallel moves and multiple Markov chains are effective approaches to parallel simulated annealing when applied to TimberWolfSC, yet speculative computation is wholly inadequate.

Parallel algorithms developed for CAD problems today suffer from two important drawbacks. First, they are machine specific, and tend to perform poorly on architectures other than the one for they were designed. Second, the quality of results degrades significantly during parallel execution. In this paper, we address these two problems for an important CAD application: test generation for sequential circuits, We have developed a new parallel test generator, ProperTEST, that is portable across a range of MIMD parallel architectures. This work is part of the ProperCAD project which aims to develop CAD algorithms that run unchanged on shared and nonshared memory machines. We present performance data for ProperTEST on ISCAS 89 sequential circuits on a Sequent Symmetry, an Intel i860 hypercube, an NCUBE/2 hypercube, a network of Sun workstations, and an Encore Multimax. Parallel processing can also be used to improve on the fault coverage possible on one processor in a given amount of time. This was not possible in earlier approaches due to search anomalies. Using ProperTEST, we provide results on ISCAS 89 benchmark programs demonstrating the improvements in fault coverage as the number of processors is increased.

We discuss the design and implementation of task migration in the Charm parallel programming environment. Charm [7] is a language and run-time system for developing portable parallel applications for MIMD machines that supports a coarse-grained dataflow model of programming. We analyze the performance of migration in detail and demonstrate its efficiency on one nonshared memory machine: the nCUBE/2 hypercube.

Combinational logic synthesis is a very important phase of VLSI system design. But the logic synthesis process requires large computing times if near optimal quality of the logic network is desired. Parallel processing is fast becoming an attractive solution to reduce the computational time. Recently, researchers have started to investigate parallel algorithms for problems in logic synthesis and verification. Much of the work in parallel algorithms for CAD reported to date, however, suffers from a major limitation. The parallel algorithms proposed for the CAD applications are designed with a specific underlying parallel architecture in mind. Moreover, incompatibilities in programming environments also make it difficult to port these programs across different parallel machines. As a result, a parallel algorithm needs to be developed afresh for every target parallel architecture. The ongoing project of ProperCAD offers an attractive solution to that problem. It allows the development and implementation of a parallel algorithm on the CHARM runtime system such that it can be executed in all the parallel machines without any change in the program. In this paper, we describe a portable parallel algorithm for logic synthesis based on the Transduction method, called ProperSYN. This algorithm uses an asynchronous message driven data-flow model of computation, with no explicit synchronizing barriers separating different phases of parallel computation as used in many previously developed parallel algorithms. Our algorithm is therefore more scalable to large numbers of processors. The algorithm has been implemented and it runs on a variety of parallel machines. We present results on several benchmark circuits for shared memory MIMD machines like Sequent Symmetry and Encore Multimax, distributed memory MIMD machine like the Intel/860 hypercube and distributed processing systems like networks of SUN workstations.>

Most parallel algorithms for VLSI CAD proposed to date work efficiently only on machines that they were designed for. As a result, these algorithms are dependent on the architecture for which they are developed and do not port easily to other parallel architectures. In an effort to address this problem, we are developing a Portable object-oriented parallel environment for CAD algorithms (ProperCAD). The objectives of this research are two-fold: 1) To develop new parallel algorithms that run in a portable object-oriented environment. We accomplish this in two stages. First, we develop CAD algorithms using a general purpose platform for portable parallel programming called CHARM developed at the University of Illinois. Concurrently, we are developing a C++ environment that is truly object-oriented and specialized for CAD applications; and 2) To design the parallel algorithms around a good sequential algorithm with a well-defined parallel-sequential interface. This will permit the parallel algorithm to benefit from future developments in sequential algorithms. This approach is described using one CAD application that has been implemented as part of this project-ProperEXT: a flat extractor for VLSI circuits. The algorithm, its implementation, and performance of ProperEXT on a range of parallel machines is presented. The implementation is portable across a variety of parallel platforms without change. It currently runs on an Encore Multimax, a Sequent Symmetry, Inter iPSC/2 and i860 hypercubes, a NCUBE 2 hypercube and a network of Sun Sparc workstations.>

We describe a binding environment for the AND and OR parallel execution of logic programs that is suitable for both shared and nonshared memory multiprocessors. The binding environment was designed with a view of rendering a compiler using this binding environment machine independent. The binding environment is similar to closed environments proposed by J. Conery. However, unlike Conery's scheme, it supports OR and independent AND parallelism on both types of machines. The term representation, the algorithms for unification and the join algorithms for parallel AND branches are presented in this paper. We also detail the differences between our scheme and Conery's scheme. A compiler based on this binding environment has been implemented on a platform for machine independent parallel programming called the Chare Kernel.>

For pt.I. see ibid., p. 170-80. In pt.I, we presented a binding environment for the AND and OR parallel execution of logic programs. This environment was instrumental in rendering a compiler for the AND and OR parallel execution of logic programs machine independent. In this paper, we describe a compiler based on the Reduce-OR process model (ROPM) for the parallel execution of Prolog programs, and provide performance of the compiler on five parallel machines: the Encore Multimax, the Sequent Symmetry, the NCUBE 2, the Intel i860 hypercube and a network of Sun workstations. The compiler is part of a machine independent parallel Prolog development system built on top of a run time environment for parallel programming called the Chare kernel, and runs unchanged on these multiprocessors. In keeping with the objectives behind the ROPM, the compiler supports both on and independent AND parallelism in Prolog programs and is suitable for execution on both shared and nonshared memory machines. We discuss the performance of the Prolog compiler in some detail and describe how grain size can be used to deliver performance that is within 10% of the underlying sequential Prolog compiler on one processor, and scale linearly with increasing number of processors on problems exhibiting sufficient parallelism. The loose coupling between parallel and sequential components makes it possible to use the best available sequential compiler as the sequential component of our compiler.>

An algorithm based on the transduction method and implemented in the ProperCAD environment is described. The parallel ProperSYN algorithm attempts to make the execution time manageably small. The algorithm uses an asynchronous message driven computing model with no synchronizing barriers, and hence it is scalable to a larger number of processors. Also, the algorithm is portable across a wide variety parallel machines. Experimental results on various parallel machines are presented. The algorithm is built around a well-defined sequential algorithm interface such that there can be benefits from future expansion of the sequential algorithm.>

A parallel test generation algorithm, ProperTEST, for sequential circuits that is portable across a range of MIMD parallel architectures is discussed. It uses prioritized execution to ensure consistent speedups as the number of processors is increased. This consistency is achieved without loss of fault coverage with increase in the number of processors. This also permits the use of parallel processing to improve the fault coverage when the execution time is bounded. Results on ISCAS 89 benchmark programs are provided on a shared memory machine, a message passing machine, and a network of workstations. ProperTEST was run unchanged on these different architectures.>

A portable object-oriented parallel environment for CAD algorithms (ProperCAD) is described. The objectives of this research are twofold: to develop parallel algorithms that are portable and to design the parallel algorithms around a good sequential algorithm with a well-defined parallel-sequential interface, permitting the parallel algorithm to benefit from future developments in sequential algorithms. The first is achieved by writing the algorithms using the ProperCAD environment, a library of functions that permits portability of parallel CAD algorithms across MIMD machines. Programs written using this environment run unchanged on all parallel machines for which this environment is available.>

We have designed and implemented a compiler for the parallel execution of Prolog programs as a machine independent application on top of a run time environment for parallel programming called the Chare Kernel. The compiler is based on the Reduce-OR process model for the AND and OR parallel execution of Prolog programs and hence exploits both OR and independent AND parallelism found in Prolog programs. We describe the salient features of the parallel Prolog compiler from the viewpoint of its implementation as a Chare Kernel application. The responsibilities of process creation, load balancing, queueing strategies for work pool management, memory management and interprocess communication are all assumed by the Chare Kernel thereby eliminating these concerns at the application level. We discuss the effectiveness of this separation for a large application like the parallel Prolog compiler. The machine independence property makes the compiler easy to port on all machines, both shared and nonshared, that support the Chare Kernel. The compiler has been implemented on a variety of machines, including the Encore Multimax, the Sequent Symmetry, the Intel iPSC/2 hypercube and the Alliant FX/8. We briefly discuss its performance on a range of benchmarks exhibiting AND, OR and AND/OR parallelism on two of these machines. The speedups obtained are linear, demonstrating the effectiveness of the Chare Kernel as a simple, elegant, yet powerful environment for parallel programming.