GRAPH MODELS OF COMPUTATIONS IN COMPUTER SYSTEMS.

Abstract

A directed graph is used as a model for computational tasks. This model shows the precedence constraints, concurrency or mutual exclusiveness between subtasks. The directed graph is transformed into an acyclic graph in such a way that the mean path length of the original cycles are left unchanged. From this graph, mean path length measurements can be performed. Associated with an algorithm examining the structure of the graph, lower and upper bounds on the number of processors referred for maximum parallelism can be determined. A one-shot 'a priori' scheduling with different urgency rules is presented and tested on some example graphs. It presents a large saving of computational time compared to previous experiments. (Author)

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1968
Accession Number
AD0678753

Entities

People

  • Jean-loup E. Baer

Organizations

  • University of California, Los Angeles

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Computers
  • Energy
  • Mathematical Analysis
  • Mathematics
  • Measurement
  • Multithreading
  • Nuclear Energy
  • Scheduling (Production)

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Parallel and Distributed Computing.
  • Systems Analysis and Design