李亜民教授は、「Best Paper Award」（CITS 2019）を受賞しました。
論文「Switch Fault Tolerance in a Mirrored K-Ary N-Tree」
The fat-tree is one of the most commonly used topologies of the interconnection networks in current large-scale parallel computers. A k-ary n-tree is a fat-tree with multiple roots where k is the arity or the number of links of a switch that connects to the previous or next level; that is, the switch radix is 2k, and n is the number of levels. The compute nodes are connected only to the leaf switches. The fat-tree is a folded version of a Clos network. The Clos network is a multistage interconnection network (MIN) that uses small-scale crossbar as the building blocks. It was originally designed for non-blocking telecommunication circuit switching.
Fat-tree and Clos network provide high path diversity but meanwhile require a higher number of switches with a non-negligible wiring complexity and have a greater packet latency than other low-cost MINs. The increased switch cost and packet latency both stem from the need to route packets first to an arbitrary middle level or root switch and then to their ultimate destination.
A Mirrored K-Ary N-Tree (MiKANT) network is a variant of fat-tree aimed at reducing hardware cost and packet latency. MiKANT doubles the number of compute nodes of the fat-tree by adding a few switches and making all the switches have a same radix. Fig. 1 shows a MiKANT(k,n) with k=3 and n=3. Compared to the classical fat-tree and Clos network, MiKANT not only reduces the numbers of switches and links so that it can be implemented at lower hardware cost, but also makes the network average distance shorter for achieving higher communication performance.
As the scale of MiKANT becomes large, the probability of switch failure increases. A switch faulty means that the switch and all links connected to it cannot be used for passing the packet. Fault tolerance is one of the important issues of the interconnection networks for large-scale parallel computers. The purpose of fault tolerant routing is to find a routing path from source node to destination node with high probability in a system with switch or link faulty.
Fat-tree is widely used in recent designs of supercomputers. As a variant of fat-tree, the MiKANT network can achieve high performance at low implementation cost. The proposed three simple fault tolerant routing algorithms are deadlock-free and can find a path between source and destination nodes at high probability. The future research work may include the link fault tolerant routing in MiKANT and implementation of MiKANT on a chip.
李 亜民 教授（LI Yamin）
LI Yamin Born in China in 1958. Graduated from the Department of Computer Science and Engineering, Tsinghua University, and got a Ph.D degree from the Graduate School of Computer Science and Technology, Tsinghua University. After working as an assistant and associate professor at Tsinghua University, and associate professor at the University of Aizu, he became a professor at the Department of Computer Science, the Faculty of Computer and Information Sciences, Hosei University in April 2000.