A novel concurrent cache-friendly binary decision diagram construction for multi-core platforms
A novel concurrent cache-friendly binary decision diagram construction for multi-core platforms
复制标题
一种适用于多核平台的新型并发缓存友好的二元决策图构建
DOI：
10.7873/date.2013.291
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Mustafa ElNainay
中科院分区：
文献类型：
--
作者：
Mahmoud Elbayoumi;M. Hsiao;Mustafa ElNainay
目前，像CUDD这样的BDD包依赖于链式哈希表。虽然它们在内存使用方面是有效的，但由于动态分配和数据间接，它们表现出较差的缓存性能。此外，它们对并发环境的吸引力较小，因为它们需要线程安全的垃圾收集器。此外，为了利用多核平台的优势，最好重新设计底层算法，例如传统的深度优先搜索（DFS）构造，广度优先搜索（BFS）构造，还是混合BFS与DFS的构造将是最好的。在本文中，我们介绍了一种新的BDD包友好的多核平台上，建立在一些算法。首先，我们使用并发友好的Hopscotch哈希来重新构造唯一表（UT），以提高缓存性能。其次，我们用跳房子散列法重新设计BFS哈希。第三，我们提出了一种新的技术，利用BFS的同时工作作为一个计算表（CT）。最后，我们提出了一种新的增量标记清除垃圾收集器（GC）。我们报告的结果BFS和混合BFS-DFS的建设方法。通过这些技术，即使是单线程BDD，与传统的单线程CUDD包相比，我们也能够实现高达8倍的加速比。当启动两个线程时，又获得了1.5倍的加速。
Currently, BDD packages such as CUDD depend on chained hash tables. Although they are efficient in terms of memory usage, they exhibit poor cache performance due to dynamic allocation and indirections of data. Moreover, they are less appealing for concurrent environments as they need thread-safe garbage collectors. Furthermore, to take advantage of the benefits from multi-core platforms, it is best to re-engineer the underlying algorithms, such as whether traditional depth-first search (DFS) construction, breadth-first search (BFS) construction, or a hybrid BFS with DFS would be best. In this paper, we introduce a novel BDD package friendly to multicore platforms that builds on a number of heuristics. Firstly, we re-structure the Unique Table (UT) using a concurrency-friendly Hopscotch hashing to improve caching performance. Secondly, we re-engineer the BFS Queues with hopscotch hashing. Thirdly, we propose a novel technique to utilize BFS Queues to simultaneously work as a Computed Table (CT). Finally, we propose a novel incremental Mark-Sweep Garbage Collector (GC). We report results for both BFS and hybrid BFS-DFS construction methods. With these techniques, even with a single-threaded BDD, we were able to achieve a speedup of up to 8× compared to a conventional single-threaded CUDD package. When two-threads are launched, another 1.5× speedup is obtained.
DOI：
10.12694/scpe.v11i4.663
发表时间：
2010
期刊：
Scalable Comput. Pract. Exp.
影响因子：
--
作者：
Jie Cheng
通讯作者：
Jie Cheng