Scientists develop algorithm for more reliable processors in data centers

Researchers from HSE MIEM and Samara University have developed the LRF-3D algorithm to automatically bypass idle nodes in three-dimensional networks-on-chip. Thanks to its hierarchical architecture, the algorithm outperforms existing solutions in both speed and path accuracy, improving processor reliability for use in data centres, supercomputers, and AI computing. The source code and test results are publicly available.

Multiprocessor systems-on-chip (MPSoCs) are electronic circuits that integrate thousands of computing elements into a single microchip connected by an on-chip communication network. Such systems are used in data centres, supercomputers, and AI computing. 

Manufacturing defects or crystal degradation can cause individual network nodes to malfunction, creating dead ends. Therefore, the design of the on-chip communication network must account for the need to bypass such faulty areas from the outset. 

Different algorithms can be used for signal transmission. Global algorithms can find optimal paths, but they require information about the entire network and significant computing resources. Local algorithms, by contrast, consider only the nearest neighbours and therefore often generate longer paths than global algorithms. Researchers from the HSE MIEM Laboratory of Computer-Aided Design Systems and Samara University have proposed a hierarchy of eight local algorithms, with LRF-3D at its core. It evaluates the status of neighbouring nodes and, when it encounters a local dead end, backtracks to the previous position and eliminates the blocked direction.

'The algorithm works much like a car navigation system: if a familiar route is blocked, it immediately looks for an alternative,' explains study co-author Aleksandr Romanov, Leading Research Fellow at the HSE MIEM Laboratory of Computer-Aided Design Systems. 

To validate the algorithm’s performance, the researchers tested it under 36 scenarios divided into five functional categories, including mazes, corridors, and random failures.

The experiments show that, with up to 50% of nodes faulty, the average deviation of the LRF-3D path length from the reference A* algorithm is only 1.64%, while outperforming LOFT by more than 137 times in terms of route quality. At a failure density of 13–30%, LRF-3D successfully delivers data packets in 86% of cases. In terms of speed, LRF-3D makes routing decisions 16.7 times faster than A* and 22.5 times faster than LOFT.

'We plan to test the algorithm on real chips and assess its impact on power consumption and data transfer rates. If the results are confirmed, the technology could help create a new generation of multiprocessor systems-on-chip that operate not only faster but also much more reliably, even under challenging conditions,' says Aleksandr Romanov.