Languages, Compilers, and Run-Time Systems for Scalable Computers: 4th International Workshop, LCR ’98 Pittsburgh, PA, USA, May 28–30, 1998 Selected Papers (Lecture Notes in Computer Science, 1511)

Languages, Compilers, and Run-Time Systems for Scalable Computers
Preface
Table of Contents
Expressing Irregular Computations in Modern Fortran Dialects
	Introduction
	Expressing Irregular Computations Using Nested Data Parallelism
	Nested Data Parallelism in Fortran
	Implementation Issues
		Implementation Strategies
		Nested Parallelism Using Current Fortran Compilers
		Example
		Results
		Discussion
	Related Work
	Conclusions
	References
Memory System Support for Irregular Applications
	Introduction
	Sparse Matrix-Vector Multiplication
		Scatter/Gather
		Page Coloring
	Conclusions
	References
MENHIR: An Environment for High Performance Matlab
	Introduction
	Related Works
	Menhir\'s Target System Description (PD1OT1cmrcmrmmnnnscMTSD)
	Overview of Menhir\'s Compilation Process
		Type Analysis
		Code Generation
	Preliminary Performances
	Conclusion
	References
On the Automatic Parallelization of Sparse and Irregular Fortran Programs
	Introduction
	The Benchmark Suite
	Loop Paterns
		Overview
		Loop Patterns for Indirectly Accessed Arrays
		Other Loop Patterns
	New Transformation Techniques
		Parallelizing Loops Containing Consecutively Written Arrays
		Histogram Reduction
		Loop-pattern-aware run-time dependence test
	Experimental Results
	Related Work
	Conclusion and Future Work
	References
Loop Transformations for Hierarchical Parallelism and Locality
	Introduction
	Transformation Framework
	Algorithm for Selection of Hierarchical Parallelism and Locality
	Performing Loop Transformations after Tiling
	Performing Transformations on Parallel Loops
	Related Work
	Conclusions and Future Work
	References
Data Flow Analysis Driven Dynamic Data Partitioning
	Introduction
	Program Representation and Communication Costs
	The Partitioning Heuristic
	Experimental Results
	Conclusion and Future Work
	References
A Case for Combining Compile-Time and Run-Time Parallelization
	Introduction
	Instrumentation
	Predicated Array Data-Flow Analysis
		Extending Traditional Data-Flow Analysis
		Improving Compile-Time Analysis
		Deriving Low-Cost Run-Time Parallelization Tests
		Description of Technique
	Experimental Results
	Related Work
	Conclusion and Future Work
	References
Compiler and Run-Time Support for Adaptive Load Balancing in Software Distributed Shared Memory Systems
	Introduction
	Design and Implementation
		The Base Software DSM Library
		Compile-Time Support for Load Balancing
		Run-Time Load Balancing Support
		Example
	Experimental Evaluation
		Environment
		Load Balancing Results
		Locality-Conscious Load Balancing Results
	Related Work
	Conclusions
	References
Efficient Interprocedural Data Placement Optimisation in a Parallel Library
	Introduction
	Basic Approach
		Data Distributions
		Library Operator Placement Constraints
	Optimisation
		Calculating Required Redistributions
		A Cost Model for Redistributions
		The Algorithm
		Related Work
	Re-Using Execution Plans
		Run-Time Optimisation Strategies
		Recognising Opportunities for Reuse
		When to Re-Use and When to Optimise
	Implementation and Performance
		Comparison with Sequential, Compiled Model
		Parallel Performance
		Performance of Our Optimisations
	Conclusions
		Run-Time vs. Compile-Time Optimisation
		Related Work
		Future Work
	References
A Framework for Specializing Threads in Concurrent Run-Time Systems
	Introduction
	Thread Implementation Alternatives
	Experience with Threads in the SR Run-Time System
	Implementation Issues for Threads and Run-Time Systems
		Thread Control Blocks
		Context Switching
		Scheduling and Synchronization
	The Mezcla Thread Framework
		Thread Control Blocks
		Thread Primitives
		Thread Generation
		Performance
	Conclusions
	References
Load Balancing with Migrant Lightweight Threads
	Introduction
	Chant.
	Thread Migration
	Load Balancing
		Lower Level Load Balancing Routines
		Load Balancing Commands
		The Load Balancing Function
	Performance
		Thread Migration Performance
		Message Forwarding Performance
		Test Applications
	Conclusions and Future Work
	References
Integrated Task and Data Parallel Support for Dynamic Applications
	Introduction
	The Smart Kiosk: A Dynamic Vision Application
		Color-Based Tracking Example
	Stampede
	Integration of Task and Data Parallelism
		Static Data Parallel Strategy
		Dynamic Data Parallel Strategy
	Experimental Results
	Conclusions and Future Work
	References
Supporting Self-Adaptivity for SPMD Message-Passing Applications
	Introduction
	Abstract Machine Interface
	Initial Adaptivity
		Active Platform
		Mapping Algorithms
	Dynamic Adaptivity
	Related Work
	Conclusions
	References
Evaluating the Effectiveness of a Parallelizing Compiler
	Introduction
	Background
		Origin 2000
		Parallel Programming Environment
		Overflow
	Experimental Study
		Execution Times of the Parallel Versions
		Compilation Times
		Additional Experimental Data and Analysis
	Discussion
	Conclusions
	References
Comparing Reference Counting and Global Mark-and-Sweep on Parallel Computers
	Introduction
	Collection Algorithms and Implementations
		Local Collector and Entry Table
		Reference Counting
		Global Mark-and-Sweep
	Performance Analysis on a Simple Model
		Cost of Garbage Collection
		Analysis of Reference Counting
		Analysis of Global Mark-and-Sweep
	Experiments
		Environments
		Applications
		Results
	Related Work
	Conclusion and Future Work
	References
Design of the GODIVA Performance Measurement System
	Introduction
	Overview of Godiva Structure and Use
	Design Choices: Pro\'s and Con\'s
	Comparison with Other Systems
	Conclusions
	References
Instrumentation Database for Performance Analysis of Parallel Scientific Applications
	Introduction
	Tool Components
		Instrumentation
		Visualization
		Analysis
	Sparse Matrix Vector Product Example
		Instrumentation
		Analysis
	Conclusion
		Design Issues
		Future Work
	References
A Performance Prediction Framework for Data Intensive Applications on Large Scale Parallel Machines
	Introduction
	Data Intensive Applications Suite
		Remote Sensing - Titan and Pathfinder
		Virtual Microscope
	Application Emulators
		Case Study: An Application Emulator for Titan
	Simulation Models
		Hardware Models
		Tightly-Coupled Simulation
		Loosely-Coupled Simulation
	Experimental Evaluation of Simulation Models
	Related Work
	Conclusions
	References
MARS: A Distributed Memory Approach to Shared Memory Compilation
	Introduction
	Compiler Infra-Structure
	Data Parallel Approach
	Scalars
		Possible Solutions
		Proposed Solution
		Copy Out
		Synchronisation
		Algorithm
	Data Reshaping
		Data Transformations on Linearised Arrays
		Reducing Access Overhead for Linearised Arrays
	Experiments
	Conclusion
	References
More on Scheduling Block-Cyclic Array Redistribution
	Introduction
	Motivating Example
	The Overlapped Redistribution Problem
		Communication Model
	Graph-Theoretic Algorithms
		Complexity
		A Counter-Example
		An Efficient Heuristic
	Modular Algebra Techniques
	Conclusion
	References
Flexible and Optimized IDL Compilation for Distributed Applications
	Introduction
	Flick
	IDL Compilation for a Global Memory Service
		Khazana
		Decomposed Stubs: A New Presentation Style for CORBA
		Decomposed Stubs for Distributed Applications
	Related Work
	Conclusion
	References
QoS Aspect Languages and Their Runtime Integration
	Introduction
	Overview of Aspect-Oriented Programming
	Overview of QuO
		Execution Model of a QuO Application
		The QuO Toolkit for Building QuO Applications
	The QuO Aspect Languages and Code Generators
		Contract Description Language (CDL)
		The Structure Description Language (SDL)
	Related Work
	Conclusions
	References
The Statistical Properties of Host Load
	Introduction
	Measurement Methodology
	Statistical Analysis
	Self-Similarity
	Epochal Behavior
	Conclusions and Future Work
	References
Locality Enhancement for Large-Scale Shared-Memory Multiprocessors
	Introduction
	Memory Locality Enhancement
	Inter-Loop-Nest Locality Enhancement
	Intra-Loop-Nest Locality Enhancement
	Machine-Specific Locality Enhancement
	Concluding Remarks
	References
Language and Compiler Support for Out-of-Core Irregular Applications on Distributed-Memory Multiprocessors
	Introduction
	Language Support
	Compilation Strategies
		Basic Parallelization Strategy
		Optimizations
	Performance Results
	Related Work
	Conclusions
	References
Detection of Races and Control-Flow Nondeterminism
	Introduction
	Preliminaries
	The Protect Algorithm
	The Alter Algorithm
	Conclusion
	References
Improving Locality in Out-of-Core Computations Using Data Layout Transformations
	Introduction
	Existing Techniques
	Layout restructuring framework
		Preliminaries
		Hyperplanes and File Layouts
		Determining Optimal File Layouts
	Preliminary Results
	Related Work
	Summary and Ongoing Work
	References
Optimizing Computational and Spatial Overheads in Complex Transformed Loops
	Introduction
	CDA: A Representative Extended Transformation Framework
	Computational and Spatial Overheads
	Removing Empty Iterations
	Reducing the Overhead of Guard Computations
	Optimization of Spatial Overhead for Temporaries
	Concluding Remarks
	References
Building a Conservative Parallel Simulation with Existing Component Libraries
	1.  Introduction
	2.  Parallel Discrete Event Simulation: Protocol and Model
		2.1  Manufacturing Simulation Benchmark
	3.  Preliminary Implementation
	4.  Improved Implementation
	5.  Conclusion
	References
A Coordination Layer for Exploiting Task Parallelism with HPF
	Introduction
	Task-Parallel Structures to Coordinate HPF Tasks
	COLT HPF Implementation
	Template Examples
	Experimental Results
	Conclusions
	References
InterAct: Virtual Sharing for Interactive Client-Server Applications
	Introduction
	The Runtime Interface
		Data Declaration
		Consistency Types
	Implementation Issues
		Address Translation
		Object Modification Detection
		Consistency Maintenance
	Experimental Evaluation
	Related Work
	Conclusions
	References
Standard Templates Adaptive Parallel Library (STAPL)
	Motivation
	STAPL General Specifications
	STAPL Components Overview
		P_ranges and P_containers
		P_Forall Function Template
		Generic P_algorithms
		Adaptive Features of STAPL
		Relation to Other Work.
		References
Author Index