본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

모듈 방향 결정 문제 해결을 위한 정규화된 평균장 어닐링 알고리즘
Normalized Mean Field Annealing Algorithm for Module Orientation Problem

정균락   (홍익대학교 컴퓨터공학과UU0001569  );
  • 초록

    각 모듈들의 위치가 배치 알고리즘에 의해 결정된 후에도 모듈들을 종축 또는 횡축을 중심으로 뒤집거나 회전시킴으로써 회로의 효율성과 연결성을 향상시킬 수 있다. 고집적 회로설계의 한 단계인 모듈방향 결정 문제는 모듈간에 연결된 선의 길이의 합이 최소가 되도록 각 모듈의 방향을 결정하는 문제이다. 최근에 평균장 어닐링 방법이 조합적 최적화 문제에 사용되어 좋은 결과를 보여 주고 있다. 평균장 어닐링은 신경회로망의 따른 수렴 특성과 시뮬레이티드 어닐링의 우수한 해를 생성하는 특성이 결합된 방법이다. 본 논문에서는 정규화된 평균장 어닐링을 사용해서 모듈 방향 결정 문제를 해결하였고 실험을 통해 기존의 Hopfield 네트워크 방법과 시뮬레이티드 어닐링과 그 결과를 비교하였다. 시뮬레이티드 어닐링, 정규화된 평균장 어닐링과 Hopfield 네트워크의 총 길이 감소율은 각각 19.86%, 19.85%, 19.03%였으며, 정규화된 평균장 어닐링의 실행 시간은 Hopfield 네트워크보다는 1.1배, 시뮬레이티드 어닐링보다는 11.4배 정도 빨랐다.


  • 참고문헌 (20)

    1. M. Yamada and C. L. Liu, 'An Analytical Method for Optimal Moudle Orientation,' Proc. 1988 International Symp, on Circuits and Systems, pp 1679-1682 
    2. R. Libeskind-Hadas and C. L. Liu, 'Solution to the Module Orientation and Rotation Problem by Neural Computation Network,' Proc. 26th Design Automation Conference, pp400-405, 1989 
    3. Shigeo Abe, 'Theories on the Hopfield Neural Networks,' Proc. of IJCNN-89, Vol. 1, Jun 
    4. David E. Van Den Bout, 'Graph partitioning Using Annealed Neural Networks,' IEEE Trans. on Neural Networks, Vol. 1, No.2, June, pp 192-203, 1990 
    5. Griff Bilbro, Reinhold Mann, Thomas K, Miller, 'Optimization by Mean Field Annealing,' 
    6. Shiego Abe, 'Global Convergence and Suppression of Sputious States of the Hopfield Neural Networks,' Proc. IJCNN-91, Vol. 2, Nov. 1991 
    7. 김재범, 정균락, '최장 전선의 길이를 최소화하기 위한 모듈의 방향 결정에 관한 휴리스틱 연구', 정보과학회 논문지(A), 제 23권, 제 1 호, pp. 34-44 
    8. 도원철, 정균락, 'Hopfield 네트워크를 이용한 모듈의 방향 결정', 정보과학회 논문지, 제 21 권, 제 3 호, 3월, pp. 481-488, 1994 
    9. J. J. Hopfield and D. W. Tank, 'Neural computation of decision in optimization problems,' Biol. Cybern., Vol. 52, 1985 
    10. J. Frreman and D. Skapura, 'Neural networks,' Addison- Wesley Publishing Company, 1991 
    11. S. Kirkpatric, C. Gelatt, Jr., and M. Vecchi, 'Optimization by Simulated Annealing,' Science, Vol.220, No. 4598, pp 671 -680, 1983 
    12. P.J.M. van Laarhoven and E.H.L. Arts, 'Simulated Annealing : Theory and Applications,' Kluwer Academic Publishers, 1987 
    13. P. Stolarz, 'Merging constrained optimization with deterministic annealing to solve combinatorially hard problems,' Tech. Report, LA-UR-91_3593, Los Alamos National Lab, 1991 
    14. C. Yu and W. Lee, 'A parallel Mean Field Neural Net Approach to an Unrestricted Channel Routing Problem,' KISS Proc. of Info Science 93, 1993 
    15. D. Haockanson and S. Radu, 'An investigation of the effects of PCB_module orientation on radiated EMII,' 1999 IEEE Intl. Symp. on Electromagnetic Compatibility, vol. 1, pp 399-404, 1999 
    16. N. Funabiki, J. Kitamichi, and S. Nishikawa, 'An evolutionary neural network approach for module orientation problems,' IEEE Transaction on Systems, Man andCybernetics, Part B, vol. 28, pp 849-855, 1998 
    17. R. Chang and P. Hisiao, 'Genetic algorithm for module orientation problem,' Electronic Letters, vol 30, issue 15, pp 1199-1200, 1994 
    18. S. S. Kim and C. M. Kyung, 'Module orientation algorithm using reconstruction of nets and mean field annealing,' Electronic Letters, vol 27, issue 13, 1991 
    19. R. Liang and F.C. Kang, 'Thermal generating unit commitment using an extended mean field annealing neural network,' IEE Proceedings, Generation, Transmission and Distribution, vol 14, pp 15-22, 2000 
    20. K. Sohn, J. Kim, and W.E. Alexander, 'A mean field annealing approach to robustcorner detection',' IEEE Transaction on Systems, Man and Cybernetics, Part B, vol28, pp 82-90, 1998 

 저자의 다른 논문

  • 정균락 (12)

    1. 1992 "최적화 문제에서 그래프의 응용" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 10 (6): 37~42    
    2. 1999 "일반 트리를 미적으로 도시하기 위한 분할-정복 알고리즘" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (1): 117~124    
    3. 2003 "캐쉬 효과를 고려한 확장된 Pairing Heap 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (5): 250~257    
    4. 2008 "케이블 TV 망에서 노드 선택을 위한 휴리스틱 연구" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 13 (4): 133~140    
    5. 2010 "연결 지향 네트워크에서 최초 가용 구간을 찾는 효율적인 알고리즘" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 15 (3): 73~80    
    6. 2011 "공유 네트워크에서 SVC 비디오 스트리밍을 위한 효율적인 대역폭 관리 알고리즘" 정보과학회논문지. Journal of KIISE. 정보통신 38 (3): 243~247    
    7. 2012 "공유 네트워크에서 공유대역폭 트리 구성을 위한 선형 시간 알고리즘" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 17 (6): 93~100    
    8. 2012 "무선 센서 네트워크에서 행위 기반 공격 탐지와 보고 문제를 위한 개선된 최단 경로 트리를 사용하는 알고리즘" 정보과학회논문지. Journal of KIISE. 정보통신 39 (4): 365~370    
    9. 2013 "무선 센서 네트워크에서 행위 기반 공격 탐지를 위한 감시 노드의 연결성과 일반 노드의 커버리지 분석" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 18 (12): 27~34    
    10. 2014 "다중 서버를 사용하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 19 (6): 101~108    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기