BM/C(3) Algorithm Mapping Onto Concurrent Processors

Abstract

This report is concerned with the mapping of large scale resource allocation algorithms onto parallel computing architectures. The mapping problem is viewed as one of assigning the nodes of a finite, directed, acylic task graph (representing the logical and data dependencies among the tasks constituting the algorithm) onto the nodes of a finite, undirected processor graph (denoting the parallel computing architecture). The objective is to minimize the completion time of the algorithm such that the redundancy, processor memory and security constraints are satisfied. The delays introduced by task queueing, message transmission, message collision and precedence constraints are explicitly modeled. We present four algorithms to solve the mapping problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1989
Accession Number
ADA207877

Entities

People

  • Krishna R. Pattipati
  • Peter B. Luh
  • Rong-tay Lee
  • Samir Shah
  • Somanth Deb

Organizations

  • University of Connecticut

Tags

Communities of Interest

  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computer Architecture
  • Computer Programming
  • Computer Programs
  • Computers
  • Control Systems
  • Directed Energy Weapons
  • Gantt Charts
  • Heuristic Methods
  • Integer Programming
  • Multitarget Tracking
  • Operating Systems
  • Optimization
  • Parallel Computing
  • Parallel Processing
  • Target Tracking

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Networking
  • Graph Algorithms and Convex Optimization.