• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >A Novel {O(n)} Parallel Banker's Algorithm for System-on-a-Chip
【24h】

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

机译：片上系统的新型{O（n）}并行Banker算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：本文提出了一种新颖的O（n）并行Banker算法（PBA），它是Banker算法（BA）（一种著名的O（mtimes n）避免死锁算法）的并行版本。我们在硬件中实现该方法，我们称之为PBA单元（PBAU）。 PBAU不仅仅是BA的Verilog HDL转换，而是一种新颖的，完全面向硬件的实现，它利用BA中所有计算的最大硬件并行性，在最佳情况下导致O（1）运行时复杂性，在最坏情况下导致O（n） 。 PBAU是一个知识产权（IP）块，为多处理器片上系统（MPSoC）提供了一种非常快速，自动避免死锁的机制，我们预计它将成为未来高性能计算环境的主流。此外，我们的PBAU支持多实例多资源系统。我们证明，PBAU不仅可以在几个时钟周期内避免死锁（比软件中的BA快几个数量级），而且在一个特定的示例中，与避免软件死锁相比，应用程序的执行时间可提高19％。最后，由于PBAU而导致的MPSoC区域开销很小，在我们的候选MPSoC示例中，不到0.05％。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号