Publication detail

An Evolutionary Approach to Collective Communication Scheduling

JAROŠ, J. OHLÍDAL, M. DVOŘÁK, V.

Original Title

An Evolutionary Approach to Collective Communication Scheduling

English Title

An Evolutionary Approach to Collective Communication Scheduling

Type

conference paper

Language

en

Original Abstract

In this paper, we describe two evolutionary algorithms aimed at scheduling collective communications on interconnection networks of parallel computers. To avoid contention for links and associated delays, collective communications proceed in synchronized steps. Minimum number of steps is sought for the given network topology, wormhole (pipelined) switching, minimum routing and given sets of sender and/or receiver nodes. Used algorithms are able not only re-invent optimum schedules for known symmetric topologies like hyper-cubes, but they can find schedules even for any asymmetric or irregular topologies in case of general many-to-many collective communications. In most cases does the number of steps reach the theoretical lower bound for the given type of collective communication; if it does not, non-minimum routing can provide further improvement. Optimum schedules may serve for writing high-performance communication routines for application-specific networks on chip or for development of communication libraries in case of general-purpose interconnection networks.

English abstract

In this paper, we describe two evolutionary algorithms aimed at scheduling collective communications on interconnection networks of parallel computers. To avoid contention for links and associated delays, collective communications proceed in synchronized steps. Minimum number of steps is sought for the given network topology, wormhole (pipelined) switching, minimum routing and given sets of sender and/or receiver nodes. Used algorithms are able not only re-invent optimum schedules for known symmetric topologies like hyper-cubes, but they can find schedules even for any asymmetric or irregular topologies in case of general many-to-many collective communications. In most cases does the number of steps reach the theoretical lower bound for the given type of collective communication; if it does not, non-minimum routing can provide further improvement. Optimum schedules may serve for writing high-performance communication routines for application-specific networks on chip or for development of communication libraries in case of general-purpose interconnection networks.

Keywords

Collective communications, communication scheduling, evolutionary optimization.

RIV year

2007

Released

10.07.2007

Publisher

Association for Computing Machinery

Location

New York

ISBN

978-1-59593-697-4

Book

2007 Genetic and Evolutionary Computation Conference

Edition

Volume II

Pages from

2037

Pages to

2044

Pages count

8

Documents

BibTex


@inproceedings{BUT28801,
  author="Jiří {Jaroš} and Miloš {Ohlídal} and Václav {Dvořák}",
  title="An Evolutionary Approach to Collective Communication Scheduling",
  annote="In this paper, we describe two evolutionary algorithms aimed at scheduling
collective communications on interconnection networks of parallel computers. To
avoid contention for links and associated delays, collective communications
proceed in synchronized steps. Minimum number of steps is sought for the given
network topology, wormhole (pipelined) switching, minimum routing and given sets
of sender and/or receiver nodes. Used algorithms are able not only re-invent
optimum schedules for known symmetric topologies like hyper-cubes, but they can
find schedules even for any asymmetric or irregular topologies in case of general
many-to-many collective communications. In most cases does the number of steps
reach the theoretical lower bound for the given type of collective communication;
if it does not, non-minimum routing can provide further improvement. Optimum
schedules may serve for writing high-performance communication routines for
application-specific networks on chip or for development of communication
libraries in case of general-purpose interconnection networks.",
  address="Association for Computing Machinery",
  booktitle="2007 Genetic and Evolutionary Computation Conference",
  chapter="28801",
  edition="Volume II",
  howpublished="print",
  institution="Association for Computing Machinery",
  year="2007",
  month="july",
  pages="2037--2044",
  publisher="Association for Computing Machinery",
  type="conference paper"
}