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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F08%3APU76796" target="_blank" >RIV/00216305:26230/08:PU76796 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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&nbsp; 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 forthe 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

Czech name

Evoluční návrh kolektivních komunikací založený na predikci konfliktu v propojovacích sítích

Czech description

Tato práce popisuje aplikaci hybridního evolučního algoritmu na plánování kolektivních komunikací v propojovacích sítí paralelních počítačů. Zamezení zahlcení linek a s tím spojených zpoždění probíhají kolektivní komunikace v synchronních krocích. Minimální počet komunikačních kroků lze odvodit pro libovolnou topologii při využití store-and-forward přepínání minimálního směrování a dané množiny vysílačů a přijímačů. Použitý algoritmus je schopen nejenom znovu objevit optimální plány pro známe symetrickétopologie jako např. hyper-kostky, ale je také schopen nalézt plány pro asymetrické a nepravidelné topologie pro obecné many-to-many kolektivní komunikace. Ve většině případů dosahuje počet komunikačních kroků dolní teoreticky odvozené dolní meze pro daný typ kolektivní komunikace. Pokud ne, lze řešení zlepšit použitím neminimálním směrováním. Optimální plány jsou určené pro psaní vysoce výkonných k

Type

B - Specialist book

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

ISBN

978-80-214-3597-1

Number of pages

145

Publisher name

Faculty of Information Technology BUT

Place of publication

Brno

UT code for WoS book

—