Publication detail

Evolutionary design of collective communication based on prediction of conflicts in interconnection networks

OHLÍDAL, M.

Original Title

Evolutionary design of collective communication based on prediction of conflicts in interconnection networks

English Title

Evolutionary design of collective communication based on prediction of conflicts in interconnection networks

Type

book

Language

en

Original Abstract

This work describes the application of a hybrid evolutionary algorithm to scheduling collective communications on the interconnection networks of parallel computers. To avoid contention for links and associated delays, collective communications proceed in synchronized steps. The minimum number of steps is sought for any given network topology, store-and-forward switching, minimum routing and given sets of sender and/or receiver nodes. Used algorithm is able not only to re-invent optimum schedules for known symmetric topologies such as hyper-cubes, but it can find schedules even for  asymmetric or irregular topologies in case of general many-to-many collective communications. In most cases the number of steps reaches the theoretical lower bound for the given type of collective communication; if it does not, non-minimum routing can provide further improvement. Optimum schedules are destined for writing high-performance communication routines for application-specific networks on chip or communication libraries for general-purpose interconnection networks.

English abstract

This work describes the application of a hybrid evolutionary algorithm to scheduling collective communications on the interconnection networks of parallel computers. To avoid contention for links and associated delays, collective communications proceed in synchronized steps. The minimum number of steps is sought for any given network topology, store-and-forward switching, minimum routing and given sets of sender and/or receiver nodes. Used algorithm is able not only to re-invent optimum schedules for known symmetric topologies such as hyper-cubes, but it can find schedules even for  asymmetric or irregular topologies in case of general many-to-many collective communications. In most cases the number of steps reaches the theoretical lower bound for the given type of collective communication; if it does not, non-minimum routing can provide further improvement. Optimum schedules are destined for writing high-performance communication routines for application-specific networks on chip or communication libraries for general-purpose interconnection networks.

Keywords

collective communications, evolutionary optimization, interconnection network, multiprocessor

RIV year

2008

Released

29.09.2008

Publisher

Faculty of Information Technology BUT

Location

Brno

ISBN

978-80-214-3597-1

Edition

NEUVEDEN

Edition number

NEUVEDEN

Pages count

145

Documents

BibTex


@book{BUT61812,
  author="Miloš {Ohlídal}",
  title="Evolutionary design of collective communication based on prediction of conflicts in interconnection networks",
  annote="This work describes the application of a hybrid evolutionary algorithm to
scheduling collective communications on the interconnection networks of parallel
computers. To avoid contention for links and associated delays, collective
communications proceed in synchronized steps. The minimum number of steps is
sought for any given network topology, store-and-forward switching, minimum
routing and given sets of sender and/or receiver nodes. Used algorithm is able
not only to re-invent optimum schedules for known symmetric topologies such as
hyper-cubes, but it can find schedules even for  asymmetric or irregular
topologies in case of general many-to-many collective communications. In most
cases the number of steps reaches the theoretical lower bound for the given type
of collective communication; if it does not, non-minimum routing can provide
further improvement. Optimum schedules are destined for writing high-performance
communication routines for application-specific networks on chip or communication
libraries for general-purpose interconnection networks.",
  address="Faculty of Information Technology BUT",
  chapter="61812",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Faculty of Information Technology BUT",
  year="2008",
  month="september",
  pages="0--0",
  publisher="Faculty of Information Technology BUT",
  type="book"
}