### Abstract

In parallel and distributed computing, mapping a task graph to a specific multiprocessor topology is an important problem. In this paper we investigate a special case of this problem for linear task graph and linear array multiprocessors. A polynomial time sequential algorithm and a parallel algorithm are developed and analyzed. It has been shown that the sequential algorithm developed has a time complexity at least as aood as the existing n log rz algorithm while the parallel algorithm presents the very first attempt at parallelizing the sequential solution. Further, we have proved that the partitioning problem is NP-complete for tree task graphs. Applications of the algorithm are briefly discussed.

Original language | English (US) |
---|---|

Title of host publication | 1994 ACM Symposium on Applied Computing, SAC 1994 |

Publisher | Association for Computing Machinery |

Pages | 473-477 |

Number of pages | 5 |

ISBN (Electronic) | 0897916476 |

DOIs | |

State | Published - Apr 6 1994 |

Event | 1994 ACM Symposium on Applied Computing, SAC 1994 - Phoenix, United States Duration: Mar 6 1994 → Mar 8 1994 |

### Publication series

Name | Proceedings of the ACM Symposium on Applied Computing |
---|---|

Volume | Part F129433 |

### Other

Other | 1994 ACM Symposium on Applied Computing, SAC 1994 |
---|---|

Country | United States |

City | Phoenix |

Period | 3/6/94 → 3/8/94 |

### Keywords

- Computational complexity
- Load balancing
- Multiprocessors
- Parallel algorithms
- Task graph partitioning

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'A parallel algorithm for mapping a special class of task graphs onto linear array multiprocessors'. Together they form a unique fingerprint.

## Cite this

*1994 ACM Symposium on Applied Computing, SAC 1994*(pp. 473-477). (Proceedings of the ACM Symposium on Applied Computing; Vol. Part F129433). Association for Computing Machinery. https://doi.org/10.1145/326619.326815