Annual Review of Scalable Computing

The following sections are included:

• Preface

• Contents

The following sections are included:

• Introduction

• The MLMV Methodology
  • Activity Levels and ViewPoints

• Coordination Graphs: Graph Grammar Based Technique For Coordination Description
  • The CG-based Coordination Description Formalism
  • The Hierarchical Coordination Model For Concurrency Management
  • The Linear Coordination Model For Information Sharing Management

• MLMV Software Support For Implementing Distributed Cooperative Applications
  • A CORBA-based Software Environment For MLMV Models Enactment
  • Application to Distributed Editing Using the Web

• Conclusion

• Acknowledgements

• Bibliography

The following sections are included:

• Introduction

• Shared Memory Languages
  • Orca
  • Linda
  • OpenMP
  • Java

• Distributed Memory Languages
  • PVM
  • MPI
  • HPF
  • CILK
  • C*
  • ZPL

• Object-oriented Parallel Languages
  • MPL
  • Concurrent Aggregates
  • HPC++
  • Distributed Java

• Parallel Declarative Languages
  • Parallel Logic Languages
  • Parallel Functional Languages

• Composition Based Languages
  • SkieCL
  • BSPlib
  • PCN
  • CC++

• Discussion and Future Trends

• Conclusions

• Bibliography

The following sections are included:

• Introduction

• Why Java?
  • Concerns

• Parallel Computing Using Java
  • Java Applets Implementations
    • Critique
  • Standalone Java Applications
    • Critique

• Project JAVM
  • Goals
  • Transfer Policy
  • Information Policy
  • Placement Policy
  • Security in JAVM
    • JCA/JCE and the DSTC Security Provider
    • Cryptography in JAVM
  • Preliminary Results
  • Ongoing Work

• Summary

• Bibliography

The following sections are included:

• Introduction

• Datarol Architecture
  • Concept of Datarol
  • Optimization of Datarol Architecture

• Datarol-II Program
  • Instruction Set
  • Sample Program

• Datarol-II Processor
  • Overview of Datarol-II Processor
  • Memory Unit
  • Function Unit
  • Structure Memory Unit
  • Function Call Mechanism

• Evaluation of Datarol-II Architecture
  • Threading Effect
  • Effect of Implicit Register Loading
  • Swapping Cost

• Cost-Effective Implementation of Datarol-II Processor
  • FMD: Fine-grain Message Driven mechanism
  • FMP: Fine-grain Message Processor
  • Co-processing between CPU and FMP
    • Synchronization
    • Thread Queue Management
    • Frame Management
  • Preliminary Evaluation
    • An Implementation of FMD: KUMP/D
    • Performance Analysis
    • Performance of Message Handling

• Related Work

• Conclusions

• Bibliography

The following sections are included:

• Introduction
  • Scheduling Models
  • Performance Considerations
  • Contributions

• The DAG Scheduling Problem
  • The DAG Model
  • Generation of a DAG
  • Variations in the DAG Model
  • The Multiprocessor Model

• NP-Completeness of the DAG Scheduling Problem

• A Taxonomy of DAG Scheduling Algorithms

• Basic Techniques in DAG Scheduling

• Characteristics of Scheduling Algorithms

• Description of the Algorithms
  • Scheduling DAGs with Restricted Structures
    • Hu's Algorithm for Tree-Structured DAGs
    • Coffman and Graham's Algorithm for Two-Processor Scheduling
    • Scheduling Interval-Ordered DAGs
  • Scheduling Arbitrary DAGs without Communication
    • Level-based Heuristics
    • A Branch-and-Bound Approach
    • Analytical Performance Bounds for Scheduling without Communication
  • UNC Scheduling
    • Scheduling of Primitive Graph Structures
    • The EZ Algorithm
    • The LC Algorithm
    • The DSC Algorithm
    • The MD Algorithm
    • The DCP Algorithm
    • Other UNC Approaches
    • Theoretical Analysis for UNC Scheduling
  • BNP Scheduling
    • The HLFET Algorithm
    • The ISH Algorithm
    • The MCP Algorithm
    • The ETF Algorithm
    • The DLS Algorithm
    • The LAST Algorithm
    • Other BNP Approaches
    • Analytical Performance Bounds of BNP Scheduling
  • TDB Scheduling
    • The PY Algorithm
    • The LWB Algorithm
    • The DSH Algorithm
    • The BTDH Algorithm
    • The LCTD Algorithm
    • The CPFD Algorithm
    • Other TDB Approaches
  • APN Scheduling
    • The Message Routing Issue
    • The MH Algorithm
    • The DLS Algorithm
    • The BU Algorithm
    • The BSA Algorithm
    • Other APN Approaches
  • Scheduling in Heterogeneous Environments
  • Mapping Clusters to Processors

• Some Scheduling Tools
  • Hypertool
  • PYRROS
  • Parallax
  • OREGAMI
  • PARSA
  • CASCH
  • Commercial Tools

• Benchmarking the Scheduling Algorithms
  • Peer Set Graphs
  • Random Graphs with Optimal Solutions
  • Random Graphs with Pre-Determined Optimal Schedules
  • Random Graphs without Optimal Schedules
  • Traced Graphs

• Performance Results and Comparison
  • Results for the Peer Set Graphs
  • Results for RGBOS benchmarks
  • Results for the RGPOS Benchmarks
  • Results for the RGNOS Benchmarks
    • Comparing Schedule Lengths
    • Pair-Wise Comparison
    • Best Solutions and Degradations from the Best
    • Number of Processors Used
    • Algorithm Running Times
  • Results for Traced Graphs
  • Scheduling Scalability (SS)

• New Ideas and Research Trends
  • Scheduling using Genetic Algorithms
  • Randomization Techniques
  • Parallelizing a Scheduling Algorithm
  • Future Research Directions

• Summary and Concluding Remarks

• Acknowledgments

• Bibliography