Seminar 2017-06-07

Date: 2017-06-07

Time: 11:00-12:00

Speaker: Masoumeh (Azin) Ebrahimi, Senior Researcher at KTH Royal Institute of Technology

Title: EbDa: A New Theory on Design and Verification of Deadlock-free Interconnection Networks (to appear in ISCA 2017)

Abstract
In the interconnection network domain, there are two main theories, proposed by William J. Dally (Stanford University) in 1987 and José Duato (Polytechnic University of Valencia) in 1993. Many works have adapted Dally and Duato’s theories to design high-performance and adaptive networks for parallel computing systems. Some of them have had huge impact on commercial systems for example: on-chip parallel systems (GPUs, many-cores like Tilera, Xeon Phi etc.) and supercomputers (Cray T3E, Cray Black Widow supercomputers, Alphaserver GS320 supercomputer, IBM BlueGene/L supercomputer, the IBM Blue- Gene/L, etc.). Our work is in the direction of the Dally’s theory and based on the reviewer’s comment it is the most fundamental work after three decades since 1987.

A key concept in the Dally’s theory is avoiding cyclic channel dependency graph in order to guarantee a deadlock-free network. Due to the complexity of finding acyclic channel dependency graph, the usage of this theory was limited to networks with a low number of channels. Assuming a 2D network with two channels per dimension, 65,536 (4^8) combinations should be verified to find a cycle-free set of turns. In 3D network with two channels per dimension this number increases to more than 200 trillion combinations! In our theory, given the number of channels and topology, the sets of compatible turns can be directly extracted and a deadlock-free network can be designed. Also, any routing algorithm can be simply verified on its freedom from deadlock.

We believe that the usage of the proposed theory is not limited to interconnection networks but to the other areas where designing an acyclic channel dependency graph is an objective.

Bio
Masoumeh (Azin) Ebrahimi received her PhD degree with honours from University of Turku, Finland in 2013 and MBA in 2015. Later she received three projects from Vinnova-MarieCurie 2013, Academy of Finland 2014, and VR 2016. She is currently a senior researcher at KTH Royal Institute of Technology, Sweden. Her scientific work contains more than 80 publications including book chapters, journal articles and conference papers. She actively acts as a guest editor, organizer, and program chair in different workshops and conferences in the NoC and SoC areas.