A Novel O(n) Parallel Banker's Algorithm for System-on-a-Chip Export

@article{LeeMooney06, abstract = {This article proposes a novel O(n) Parallel Banker's Algorithm (PBA), which is a parallelized version of the Banker's Algorithm (BA), a well-known O(mtimes n) deadlock avoidance algorithm. We implement the approach in hardware, which we call PBA Unit (PBAU). PBAU is not a mere Verilog HDL translation of BA, but a novel, fully hardware-oriented implementation exploiting maximum hardware parallelism of all computations in BA, resulting in O(1) runtime complexity in the best case and O(n) in the worst. PBAU is an Intellectual Property (IP) block that provides a mechanism of very fast, automatic deadlock avoidance for Multiprocessor System-on-a-Chip (MPSoC), which we predict will be the mainstream of future high performance computing environments. Furthermore, our PBAU supports multiple instance multiple resource systems. We demonstrate that PBAU not only avoids deadlock in a few clock cycles (several orders of magnitude faster than BA in software), but also achieves, in a particular example, a 19 percent speedup of application execution time over avoiding deadlock in software. Lastly, the MPSoC area overhead due to PBAU is small, less than 0.05 percent in our candidate MPSoC example.}, author = {Lee, J. J. and Mooney, V. J.}, citeulike-article-id = {1001820}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1717401}, journal = {Parallel and Distributed Systems, IEEE Transactions on}, keywords = {banker, bloqueos, citas, deadlock, hardware}, number = {12}, pages = {1377--1389}, posted-at = {2006-12-19 11:04:52}, priority = {2}, title = {A Novel O(n) Parallel Banker's Algorithm for System-on-a-Chip}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1717401}, volume = {17}, year = {2006} }

TY - JOUR ID - LeeMooney06 L3 - citeulike-article-id:1001820 N2 - This article proposes a novel O(n) Parallel Banker's Algorithm (PBA), which is a parallelized version of the Banker's Algorithm (BA), a well-known O(mtimes n) deadlock avoidance algorithm. We implement the approach in hardware, which we call PBA Unit (PBAU). PBAU is not a mere Verilog HDL translation of BA, but a novel, fully hardware-oriented implementation exploiting maximum hardware parallelism of all computations in BA, resulting in O(1) runtime complexity in the best case and O(n) in the worst. PBAU is an Intellectual Property (IP) block that provides a mechanism of very fast, automatic deadlock avoidance for Multiprocessor System-on-a-Chip (MPSoC), which we predict will be the mainstream of future high performance computing environments. Furthermore, our PBAU supports multiple instance multiple resource systems. We demonstrate that PBAU not only avoids deadlock in a few clock cycles (several orders of magnitude faster than BA in software), but also achieves, in a particular example, a 19 percent speedup of application execution time over avoiding deadlock in software. Lastly, the MPSoC area overhead due to PBAU is small, less than 0.05 percent in our candidate MPSoC example. IS - 12 JF - Parallel and Distributed Systems, IEEE Transactions on EP - 1389 TI - A Novel O(n) Parallel Banker's Algorithm for System-on-a-Chip VL - 17 SP - 1377 KW - banker KW - bloqueos KW - citas KW - deadlock KW - hardware AU - Lee, JJ AU - Mooney, VJ PY - 2006/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1717401 ER -