Re: Help! What is "PYRROS"? Thanks! (Paul Havlak)
Wed, 11 Jan 1995 04:59:40 GMT

          From comp.compilers

Related articles
Help! What is "PYRROS"? Thanks! (1994-12-30)
Re: Help! What is "PYRROS"? Thanks! (1995-01-11)
| List of all articles for this month |

Newsgroups: comp.compilers,comp.parallel,comp.programming
From: (Paul Havlak)
Keywords: tools, parallel
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
References: 94-12-151
Date: Wed, 11 Jan 1995 04:59:40 GMT

Guan-Joe <> wrote:
> When I study some compiler environments, they mention there is a tool
>,called "PYRROS". But, I do not know what is it. ...

PYRROS is a system developed at Rutgers. The International Conference on
Supercomputing in '92 included a paper describing it, "PYRROS: Static Task
Scheduling and Code Generation for Message Passing Multiprocessors", by
Tao Yang and Apostolos Gerasoulis, and (althought Yang appears now to be at UCSB).

I could describe it further, but perhaps you should contact the authors
or examine the technical reports available online from Rutgers -- at
least two relevant ones are at URL

I've included their abstracts below.


Efficient Algorithms and a Software Tool for Scheduling Parallel Computation.

Apostolos Gerasoulis, Rutgers University
Tao Yang, University of California at Santa Barbara\\


To parallelize an application program for a distributed memory
architecture, we can use a precedence task graph to represent the
parallelism of this program, schedule tasks onto the given physical
processors and then distribute program and data accordingly. In this
chapter, we discuss program partitioning techniques for constructing task
graphs and present several static scheduling algorithms that consider the
overhead of inter-processor communication. Finally we give an overview of
a software system PYRROS that uses scheduling algorithms to generate
parallel code for distributed memory parallel machines.

DCS-TR-299, May 1993
Tao Yang
Scheduling and Code Generation for Parallel Architectures
(Ph.D. Dissertation)

Automatic partitioning, scheduling and code generation are of major
importance in the development of compilers for massively parallel
architectures. In the first part of this thesis, we consider compile-time
static scheduling when communication overhead is not negligible. We
provide a new quantitative analysis of granularity issues to identify the
impact of partitioning on optimal scheduling. We propose a new algorithm
for scheduling on an unbounded number of processors named DSC, which
outperforms existing algorithms in both complexity and performance.
Furthermore, we study algorithms for scheduling on a bounded number of
processors based on a multistep approach. We use DSC to cluster tasks and
then use a load balancing and physical mapping heuristic to map the
clusters onto processors. Finally we introduce a new task ordering
algorithm that tries to minimize parallel time and overlap communication
with computation. We present theoretical and experimental results to
verify the performance of these algorithms.

In the second part of the thesis, we consider the code generation problem
for message passing architectures. We propose a new optimized method for
code generation in executing a schedule of an arbitrary task graph based
on an asynchronous communication model. We optimize code by reducing
communication overhead, eliminating redundant communication and improving
memory utilization. We present a correctness analysis of the generated
code to assure data coherence and deadlock-free communication. We also
present a new multicasting algorithm for a hypercube that eliminates
unnecessary routing processors.

We have implemented a compiler tool system named PYRROS that integrates
the above algorithms for scheduling and code generation. The input of
this system is a C program with annotated dependence information and the
output is optimized parallel C code for nCUBE-I, nCUBE-II and iPSC/860
machines. The experimental results show that the performance of
automatically produced code is comparable with that of hand-written code.

Paul Havlak Dept. of Computer Science, A.V. Williams Bldg
Postdoctoral Research Associate U. of Maryland, College Park, MD 20742-3255
High-Performance Systems Lab (301) 405-2697 (fax: -2744)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.