Home| Contact Us| New Journals| Browse Journals| Journal Prices| For Authors|

Print ISSN: 2230 – 8776
Online ISSN:


  About JISM
  DLINE Portal Home
Home
Aims & Scope
Editorial Board
Current Issue
Next Issue
Previous Issue
Sample Issue
Upcoming Conferences
Self-archiving policy
Alert Services
Be a Reviewer
Publisher
Paper Submission
Subscription
Contact us
 
  How To Order
  Order Online
Price Information
Request for Complimentary
Print Copy
 
  For Authors
  Guidelines for Contributors
Online Submission
Call for Papers
Author Rights
 
 
RELATED JOURNALS
Journal of Digital Information Management (JDIM)
Journal of Multimedia Processing and Technologies (JMPT)
International Journal of Web Application (IJWA)

 

 
Journal of Information & Systems Management (JISM)

BDD Package Implementation for Computational Distribution in CPU And GPU
Miloš M. Radmanovic, Dušan B. Gajic
Miloš M. Radmanovic, Dušan B. Gajic
Abstract: Binary Decision Diagram (BDD) construction and manipulation is an important part of CAD tasks. One of the ways to improve BDD package performance is to perform certain BDD operations in parallel with the GPU. The recent development of GPU frameworks for general-purpose programming, such as OpenCL or Nvidia CUDA, has made GPUs a very powerful and attractive option for developing high-performance numerical applications. This paper proposes an efficient implementation of the BDD package that distributes computational workloads over CPUs and GPUs. This implementation takes advantage of various parallelism sources found in the BDD package. The experimental results demonstrate that implementing this solution results in significant computational speedups.
Keywords: Binary Decision Diagrams, BDD Package, Parallel Implementation, Graphics Processing Unit, GPU Computing
DOI:https://doi.org/10.6025/jism/2024/14/1/1-7
Full_Text   PDF 833 KB   Download:   7  times
References:

[1] Brace, K., Rudell, R., Bryant, R. (1990). Efficient implementation of a BDD package. In Proc. Design Automation Conf. (pp. 40-45).
[2] Sangavi, J., Ranjan, R., Bryton, R., Sangiovanni-Vincentelli, A. (1996). High performance BDD package based on exploiting memory hierarchy. In Proc. of the Design Automation Conf.
[3] Long, D. (1998). The design of cache-friendly BDD library. In Proc. 1998 IEEE/ACM Intl. Conf. on CAD (pp. 639-645).
[4] Janssen, G. (2001). Design of pointerless BDD package. 10th Int. Workshop on Logic & Synthesis, Lake Tahoe, USA.
[5] Ebendt, R., Gorschwin, F., Drechsler, R. (2005). Advanced BDD Minimization. Springer, New York.
[6] Janssen, G. (2003). A consumer report on BDD packages. In Proc. 16th Symp. Integrated Circuits and Systems Design (pp. 217-223).
[7] Somenzi, F. (2001). Efficient manipulation of decision diagrams. Int. J. Software Tools for Technology Transfer (STTT), 3(2), 171-181.
[8] Sentovich, M. (1996). A brief study of BDD package performance. In: Proc. of the Formal Methods on CAD (pp. 389-403).
[9] Kimura, S., Clarke, E. M. (1990). A parallel algorithm for constructing binary decision diagrams. In IEEE Intl. Conf. on Computer Design: VLSI in Computers and Processors (pp. 220-223).
[10] Stornetta, T., Brewer, F. (1996). Implementation of an efficient parallel BDD package. In Proc. of Design Automation Conf., Las Vegas, USA (pp. 641-644).
[11] Yang, B., O’Hallaron, D. R. (1997). Parallel breadth-first BDD construction. 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 145-156).
[12] Caban, D., Milford, D. (1992). A parallel BDD engine for logic verification. In Proc. 5th Annual IEEE Int. ASIC Conf. and Exhibit (pp. 499-502).
[13] Ranjan, R. K., Sanghavi, J. V., Brayton, R. K., Sangiovanni-Vincentelli, A. (1996). Binary decision diagrams on network of workstations. IEEE Int. Conf. on Computer Design: VLSI in Computers and Processors (pp. 358-364).
[14] Milvang-Jensen, K., & Alan, J. (1998). BDDNOW: A parallel BDD package. In Proc. 2nd Int. Conf. on Formal Methods in Computer-Aided Design (pp. 501-507).
[15] Yuxiong, H. (2009). Multicore-enabling a binary decision diagram algorithm. Intel Software Network. Retrieved from http://software.intel.com/en-us/articles/multicore-enabling-abinarydecision-diagramalgorithm.
[16] Gulati, K., Khatri, S. (2008). Towards acceleration of fault simulation using graphics processing units. In Proc. 45th ACM/IEEE Design Automation Conference (pp. 822-827).
[17] Bertacco, V., Chatterjee, D. (2011). High performance gate-level simulation with GP-GPU computing. Int. Symp. on VLSI Design, Automation and Test, 1-3.
[18] Chatterjee, D., Bertacco, V. (2010). EQUIPE: parallel equivalence checking with GP-GPUs. IEEE Int. Conference on Computer Design, 486-493.
[19] Gajic, D., & Stankovic, R. (2011). GPU accelerated computation of fast spectral transforms. Facta Universitatis - Series: Electronics and Energetics, 24(3), 483-499.
[20] Gajic, D., Stankovic, R., & Radmanovic, M. (2012). Implementation of dyadic correlation and autocorrelation on graphics processors. Int. J. Reasoning-based Intelligent Systems (IJRIS), 4(1/2), 82-90.
[21] Yang, B. (1999). Optimizing model checking based on BDD characterization (PhD Dissertation). Carnegie Mellon University Pittsburgh, USA.
[22] Yang, B., et al. (1998). A study of BDD performance in model checking. In Proc. Formal Methods in CAD (pp. 255-289).
[23] Rudell, R. (1993). Dynamic variable ordering for ordered binary decision diagrams. In Proc. Int. Conf. on Computer-Aided Design (pp. 139–144).
[24] Klarlund, N., & Rauhe, T. (1996). BDD algorithms and cache misses. BRICS Report Series RS- 96-5, Department of Computer Science, University of Aarhus.
[25] Aamodt, T. (2009). Architecting graphics processors for non-graphics compute acceleration. In Proc. IEEE PACRIM Conf. (pp. 963-968).
[26] Ryoo, S., et al. (2008). Optimization principles and application performance evaluation of a multithreaded GPU using CUDA. In Proc. 13th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (pp. 73–82).
[27] Owens, J., et al. (2008). GPU computing. Proc. of the IEEE, 96(5), 279–299.
[28] Gaster, B., et al. (2011). Heterogeneous Computing with OpenCL. Elsevier.
[29] Rudell, R. (1993). Espresso Misc. Reference Manual Pages. Retrieved from http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.html.


Home | Aim & Scope | Editorial Board | Author Guidelines | Publisher | Subscription | Previous Issue | Contact Us |Upcoming Conferences|Sample Issues|Library Recommendation Form|

 

Copyright © 2011 dline.info