Model alternacije zaokreta kod rešetke

Abstract

U ovom redu je predstavljen delimično adaptivni algoritam rutiranja poruka u dvodimenzionalnoj rešetki, koji je otporan na uzajamno blokiranje bez uvođenja virtualnih kanala, pod nazivom "Model alternacije zaokreta". Ovaj algoritam je baziran na sofisticiranoj ideji Turn Modela, predloženoj od strane Glass-a i Ni-a [1], s tom razlikom što zabranjeni zaokreti zavise od položaja čvora u rešetki. Simulacija je sprovedena nad poznatom XY algoritmu, West-first, North-last i Negative-first algoritmima Turn Modela, i rezultati su upoređeni sa Modelom alternacije zokreta. Podrazumevana je rešetka dimenzija 16x16, uniformni saobraćaj poruka dužine 16 flita, sa geometrijskom raspodelom vremena generisanja poruka.

We present a deadlock free partial adaptive routing algorithm for 2D mesh without virtual channels, named Alternated Turn Model. This algorithm is based on sophisticated idea of Turn Model proposed by Glass and Ni [1], where the forbidden turns depends on nodes position in the mesh. Simulation have done for the well known XY routing algorithm, West-first, North-last and Negative-first algorithms of Turn Model and results are compared with Alternated Turn Model. We have considered 16x16 mesh, uniform traffic pattern of 16-flits messages, with geometrically distributed message interarrival times.