Á¤º¸°úÇÐȸ ³í¹®Áö A : ½Ã½ºÅÛ ¹× ÀÌ·Ð
Current Result Document : 1 / 2
ÇѱÛÁ¦¸ñ(Korean Title) |
¾ç¹æÇâ Á¡ÁøÀû ½ÃÇÁÆÿ¡ ±â¹ÝÀ» µÐ BDD ÃÖÀûÈ ±â¹ý |
¿µ¹®Á¦¸ñ(English Title) |
An Optimization Technique for BDD based on Bidirectional Incremental Sifting |
ÀúÀÚ(Author) |
¼Û¹®¹è
µ¿±ÕŹ
¾ç¼±¿õ
ÀåÈÆ
Moonbae Song
Gyuntak Dong
Sunwoong Yang
Hoon Chang
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 25 NO. 09 PP. 1058 ~ 1066 (1998. 09) |
Çѱ۳»¿ë (Korean Abstract) |
ÀÌÁø °áÁ¤ ´ÙÀ̾î±×·¥(BDD : Binary Decision Diagram)Àº ºÎ¿ï ÇÔ¼öÀÇ Ç¥Çö°ú Á¶ÀÛ¿¡ È¿°úÀûÀÎ ÀڷᱸÁ¶·Î¼ CAD ºÐ¾ß¿¡ ³Î¸® È°¿ëµÇ°í ÀÖ´Ù. ÀÌ·¯ÇÑ BDDÀÇ ÃÖÀûÈ ¹®Á¦´Â ƯÈ÷ ³í¸® ÇÕ¼º°ú Çü½Ä °ËÁõ ¿µ¿ª¿¡¼ ÇʼöÀûÀÎ °ÍÀ¸·Î Àνĵǰí ÀÖ´Ù. º¯¼ö ¼ø¼´Â BDDÀÇ Å©±â¿Í ÇüÅ¿¡ Á÷Á¢ÀûÀÎ ¿µÇâÀ» ¹ÌÄ¡¹Ç·Î, ÀûÀýÇÑ º¯¼ö ¼ø¼¸¦ ±¸ÇÏ´Â °ÍÀº ¸Å¿ì Áß¿äÇÑ ¹®Á¦ÀÌ´Ù. º» ³í¹®¿¡¼´Â Á¡ÁøÀû ½ÃÇÁÆÃÀ̶ó ºÎ¸£´Â ±¹ºÎ Ž»ö ±â¹ÝÀÇ »õ·Î¿î º¯¼ö ¼ø¼È ¾Ë°í¸®µëÀ» Á¦¾ÈÇÑ´Ù. Á¦¾ÈµÈ ¾Ë°í¸®µëÀº ±âÁ¸ÀÇ ½ÃÇÁÆà ¾Ë°í¸®µë¿¡¼ÀÇ Å½»ö°ø°£À» Àý¹Ý ÀÌÇÏ·Î ÁÙÀÏ ¼ö ÀÖÀ¸¸ç, ¶ÇÇÑ °è»ê ½Ã°£À» Å©°Ô °¨¼Ò½Ãų ¼ö ÀÖÀ» »Ó¸¸ ¾Æ´Ï¶ó, ¼º´É ¸é¿¡¼µµ ¿ì¼öÇÏ´Ù. ¶ÇÇÑ Á¡ÁøÀû ½ÃÇÁÆà ¾Ë°í¸®µëÀº ½ÃÇÁÆà ¾Ë°í¸®µëÀ» ºñ·ÔÇÑ ´Ù¸¥ º¯¼ö ÃÖÀûÈ ¾Ë°í¸®µë¿¡ ºñÇØ ¸Å¿ì ´Ü¼øÇϸç, ¿©·¯°¡Áö ÇüÅ·ÎÀÇ ÈÞ¸®½ºÆ½ÀÇ °³¹ßÀÌ °¡´ÉÇÏ´Ù. Á¦¾ÈµÈ ¾Ë°í¸®µëÀº ¸¹Àº º¥Ä¡¸¶Å© ȸ·Î¿¡¼ ±× È¿À²¼ºÀÌ ÀÔÁõµÇ¾ú´Ù. |
¿µ¹®³»¿ë (English Abstract) |
Binary decision diagrams (BDDs) are widely used in computer-aided design (CAD) as data structure for representation and manipulation of Boolean functions. The optimization problem of BDDs plays an important role in the area of logic synthesis and formal verification especially. Since the variable ordering has great impacts on the size and form of BDD, finding a good variable order is very important problem. In this paper, a new variable ordering schemen based on local search, called incremental sifting, is presented. The proposed algorithm reduces a search space more than a half on that of the conventional sifting algorithm in the aspect of performance. The incremental optimization algorithm is very simple than other variable reordering algorithm including the sifting algorithm, and application of using a number of heuristics is also possible. The proposed algorithm has been implemented and the efficiency has been shown using well known benchmark circuits. |
Å°¿öµå(Keyword) |
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|