One-to-one mapping of process graphs onto a hypercube

ABSTRACT

In this paper, the problem of assigning N parallel tasks onto a hypercube with N processors is considered. Three heuristics are developed to map arbitrary process graphs, in a one-to-one fashion, onto a hypercube architecture, in order to minimize the communication cost between processors:bit-toggling (BT), bit-swapping (BS), and node-swapping (NS). The effectiveness of the methods is evaluated using a number of sample process graphs, and compared with the results obtained from simulated annealing (SA). With respect to solution quality, between the three approaches proposed, the node-swapping technique is superior.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory, Verification