Parallel and Distributed Computing

We have several projects involving parallel and distributed computing. First, we are investigating the specification of properties of parallel and distributed systems. We are also investigating the use of formal specifications as the basis of visualizations of parallel and distributed programs. The visualizations can be used to facilitate the debugging and design of programs.

Next, in the area of parallel compilers, we are extending the set of unimodular transformations to loops to include families of transformations, including loop blocking and coalescing, and loop fission and fusion. The original properties of unimodular transformations are preserved in the extended set of transformation techniques. In addition, the extended set of transformations will be applicable to imperfectly nested loops.

The allocation and scheduling of processors for distributed shared memory systems is being investigated. We are examining different methods by which system throughput can be improved by supporting time shared execution within parallel jobs with clusters (of workstations) without penalizing the job turn around time.

Finally, we are investigating different algorithms that can be used for multicast communication in massively parallel computers.

Recent Papers and Presentations

  • ``A Top-down Approach to Visualization-based Debugging of Parallel Programs'' (Joseph L. Sharnowski and Betty H.C. Cheng), to appear in the poster session of Supercomputing '94, November 1994.

  • ``A Formal Approach to Modeling Expected Behavior in Parallel Program Visualizations,'' (J.L. Sharnowski and B.H.C. Cheng), Proc. of Parallel Architectures and Languages Europe (PARLE'94), Lecture Notes in Computer Science, vol. 817, Springer Verlag, pp. 202-213, July 1994.

  • ``A Formally-based Expected Behavior Model for Parallel Program Visualizations'' (Joseph L. Sharnowski and Betty H.C. Cheng), submitted for publication, April 1994.

  • ``Data``A Temporal Model for Transparent Monitoring of Shared-Memory Multiprocessors'' (David F. Robinson and Betty H.C. Cheng) Proc. of the IEEE 17th Annual International Computer Software and Applications Conference, pp. 388-394, November 1993.

  • ``Data Parallel Program Visualizations from Formal Specifications'' (M.V. LaPolla, J.L. Sharnowski, B.H.C. Cheng, and K. Anderson), Journal of Parallel and Distributed Computing, Vol. 18, No. 2, pp. 252-257, June, 1993.

  • ``Using Visualizations to Guide Data Partitioning'' (J.L. Sharnowski and Betty H.C. Cheng) Technical Report, Michigan State University, Department of Computer, CPS-93-19, May 1993.

  • ``A Transparent Monitoring Tool for Shared-Memory Multiprocessors,'' (David F. Robinson, Betty H.C. Cheng, and Richard J. Enbody), Proc. of 16th Annual International Computer Software and Applications Conference, pp. 227-232, September 1992.

  • ``Mapping Formal Specifications to Parallel Program Visualizations'' (J.L. Sharnowski, M.V. LaPolla and Betty H.C. Cheng), Proc. of Minnowbrook Workshop on Software Engineering for Parallel Computing, pp. 29-34. August 1992.

  • ``Using Formal Specifications to Generate Visualizations of Data Parallelism'' (M.V. LaPolla, J.L. Sharnowski, Betty H.C. Cheng, and K. Anderson), Michigan State University Technical Report, MSU-CPS-92-05, July 1992.

  • ``Scalable Multicast Communication in Massively Parallel Computers'', David F. Robinson, PhD thesis, August 1994.

  • ``Temporal Specification Systems for Distributed Systems'', William E. McUmber, MS Thesis, August 1993.

  • ``Contention Free 2-D Mesh Cluster Allocation in Hypercubes'' (Stephen W. Turner, Lionel M. Ni, and Betty H.C. Cheng), accepted to appear in IEEE Transactions on Computers.

  • ``Time and/or Space Sharing in a Workstation Cluster Environment'' (S.W. Turner, L. Ni, and B.H.C. Cheng), to appear in the Proc. of Supercomputing'94, November 1994.

  • ``Contention Free 2-D Mesh Cluster Allocation in Hypercubes'' (Stephen W. Turner, Lionel M. Ni, and Betty H.C. Cheng), Proc. of International Conference on Parallel Processing, pp. 125-129, August 1993.

  • ``Application of the Unimodular Approach to Loop Fission and Loop Fusion'' (David R. Chesney and Betty H.C. Cheng) presented at the Scalable High Performance Computing Conference, Knoxville, Tennessee, May 1994.

  • ``Optimal Multicast Communication in Torus Networks'' (D.F. Robinson, P.K. McKinley, and B.H.C. Cheng), in Proc. of International Conference on Parallel Processing, Vol. I, pp. 131-141, August 1994.

  • ``Efficient Collective Data Distribution in All-Port Wormhole-Routed Hypercubes'' (D. F. Robinson, D. Judd, P. K. McKinley and B.H.C. Cheng), accepted to appear in Journal of Parallel and Distributed Computing, 1994.

  • ``Efficient Collective Data Distribution in All-Port Wormhole-Routed Hypercubes'' (D. F. Robinson, D. Judd, P. K. McKinley, and B.H.C. Cheng), Proc. of Supercomputing'93, pp. 792-803, November 1993.

  • ``Extending the Unimodular Approach to Loop Blocking and Loop Coalescing'' (David R. Chesney and Betty H.C. Cheng), Michigan State University Technical Report, MSU-CPS-94-25, April 1994.

  • ``Extending the Unimodular Approach to Other Transformation Techniques'' (David R. Chesney and Betty H.C. Cheng), Michigan State University Technical Report, MSU-CPS-93-24, September 1993.

  • ``A Formal Approach to Automatic Source Code Translation for Parallel Architectures'' (D.R. Chesney and Betty H.C. Cheng), Proc. of Minnowbrook Workshop on Software Engineering for Parallel Computing, pp. 16-27, August 1992.