From: kelly@ogicse.cse.ogi.edu (Kelly Atkinson)
Newsgroups: or.general,pdx.general,ogi.general
Subject: Computer Science Colloquia
Date: 28 Sep 92 20:45:15 GMT
Article-I.D.: ogicse.43293
Distribution: or
Organization: Oregon Graduate Institute (formerly OGC), Beaverton, OR


Oregon Graduate Institute
Department of Computer Science and Engineering

COLLOQUIUM SERIES

-----------------------------------------------------------------------
Language Issues in Software Specification and Development Series
(Co-sponsored by OCATE)

A Polynomial and On-Line Data-Flow Analysis Algorithm 
   for Determining Existential Alias Invariants in the Presence 
   of Pointers and Structured Data
Alain Deutsch, Carnegie Mellon University & INRIA

Friday, October 9, 1992,  3:30 p.m.
Main Seminar Room, OGI Administration Building

PROBLEM.  Determine automatically for each point L of a program P (with 
inductive data types and side effects) an invariant that upper 
approximates possible aliases between data access paths.

APPLICATIONS.  (A) parallelisation and dependence analysis of languages 
with pointers; (B) interference checking for extensions of: (1) functional 
languages with side effects; (2) sequential languages with controlled 
parallelism; (C) compile-time garbage collection & stack allocation.

RESULT 1.  A polynomial, on-line algorithm for determining statically 
existential, non-uniform alias invariants, applicable to polymorphically 
typed first-order Standard ML programs with imperative operations.  This 
algorithm has been validated experimentally and also theoretically using 
the framework of semantic analysis by abstract interpretation due to 
Cousot & Cousot and the following new results in semantics and formal 
language theory:

RESULT 2.  A storeless semantic model of aliasing. Classical models of 
aliasing (either denotational or operational) are based on locations and 
stores.  We elaborate a semantic model of aliasing (which is exact, 
operational and small-step) for Standard ML programs which is storeless 
--  rational trees and right-regular equivalence relations are used instead.

RESULT 3.  The lattice of exponential unitary-prefix monomial relations on 
a rational subset of the free monoid is a new result about the structure of 
rational languages that generalises the structural decompositions of Samuel 
Eilenberg and R. Parikh.  Apart from alias analysis, we have also applied 
this lattice to: (1) strictness analysis, (2) analysis of logic programs.


-----------------------------------------------------------------------
A Portable Communication Benchmark Suite for Message Passing 
   MIMD Architectures
Philippe Klein, Yale University Department of Computer Science and 
   Institut Francais du Petrole (IFP), France.

Friday, October 16, 1992,  3:30 p.m.
Main Seminar Room, OGI Administration Building

Message passing benchmarking is a tedious, error-prone business. It is, 
however, a task which must be done.  The design of algorithms, 
identification of hardware and software bottlenecks, and performance 
prediction of message passing applications all require extensive 
information about communication performance. 

Most of the numerous papers concerning the benchmarking of 
interprocessor communication deal with particular or a small class of 
message passing machines.  We attempt to be more generally applicable.  
We will describe the design and implementation of a portable 
communication benchmark suite and an associated simulator which can be 
used to estimate the communication cost of a given application program. 

These benchmarks are designed to be portable across message passing 
architectures and topologies.  They fall into three categories.  The 
uniprocessor benchmarks are designed to estimate the cost of uniprocessor 
operations needed to perform or optimize communication.  The 
contentionless benchmarks are designed to explore the cost of 
communication in the absence of contention for communication resources.  
Finally, there are benchmarks to examine the cost of communication in the 
presence of contention. 

The benchmark suite is used to estimate the communication parameters 
needed by the simulator.  The simulator is used to estimate the cost of 
communications of message passing programs based on traces derived 
from running the code on some parallel machine or simulator.  We will 
give experimental results of the benchmark suite for various machines and 
describe the communication cost analysis resulting from our simulator for 
a sparse iterative solver and an elastic wave propogation code. 

This is joint work with Harry Berryman (Yale University) and William 
Gropp (Argonne National Laboratories). 
Newsgroups: or.general