close
본문으로 이동

전자 설계 자동화

위키백과, 우리 모두의 백과사전.

전자 설계 자동화(Electronic design automation, EDA)는 ECAD(electronic computer-aided design)라고도 불리며,[1] 집적 회로인쇄 회로 기판과 같은 전자 시스템을 설계하기 위한 소프트웨어 도구이다. 이러한 도구들은 칩 설계자가 전체 반도체 칩을 설계하고 분석하는 데 사용하는 설계 흐름 내에서 함께 작동한다. 현대의 반도체 칩은 수십억 개의 구성 요소를 가질 수 있으므로 EDA 도구는 설계에 필수적이다. EDA 도구에는 소프트웨어, 하드웨어 및 설계 방법론(예: 설계 서비스)으로 확장된 전체 기술 세트가 통합되어 있으며, 이 문서는 특히 집적 회로(IC)와 관련된 EDA에 대해 설명한다. 대표적 기업으론 시높시스, 케이던스 디자인 시스템즈, 지멘스 등이 있다.

역사

[편집]

초기

[편집]

초기 전자 설계 자동화는 1950년대 IBM 700/7000 시리즈 컴퓨터의 문서화와 함께 IBM의 공로로 여겨진다.[2]

IBM은 원래 IBM 704 및 705 메인프레임 컴퓨터에서 실행되었던 Automated Logic Diagram(ALD)으로 알려진 최초의 컴퓨터 지원 설계(CAD) 시스템 중 하나를 개발했다. 설계 프로세스는 엔지니어가 수동으로 논리 회로도를 작성하는 것으로 시작되었으며, 이는 나중에 표준화된 템플릿으로 전사되고 디지털 처리를 위해 천공 카드로 변환되었다.[2][3]

기계적 기하학에 집중했음에도 불구하고, IBM과 공동으로 제작된 제너럴 모터스DAC-1은 초기 인터랙티브 그래픽 기반 CAD 시스템 중 하나였으며, 복잡한 엔지니어링 데이터를 화면 기반으로 편집하는 것의 실용성을 입증했다. 이 아이디어는 IC 레이아웃 도구에 채택되었다.[4]

EDA가 개발되기 전에는 집적 회로를 손으로 설계하고 수동으로 배치했다.[5] 일부 선진적인 사업장에서는 단색 노광 이미지를 생성하는 Gerber 포토플로터용 테이프를 생성하기 위해 기하학적 소프트웨어를 사용했지만, 이조차도 기계적으로 그려진 구성 요소의 디지털 기록을 복사한 것이었다. 이 프로세스는 근본적으로 그래픽적이었으며 전자 장치에서 그래픽으로의 변환은 수동으로 이루어졌다. 이 시대의 가장 잘 알려진 회사는 Calma였으며, 이들의 GDSII 형식은 오늘날에도 여전히 사용되고 있다.[6]

1970년대 초, 개발자들은 제도 외에도 회로 설계를 자동화하기 시작했으며 최초의 배치 및 배선 도구가 개발되었다. 냉전으로 인해 개발은 종종 거의 병행하여 이루어졌다. 서구권에서는 IEEE 학술지와 Design Automation Conference가 당시 개발의 대다수를 목록화했으며,[5] 1973년 무렵에는 분야의 발전을 추적하기 위해 방대한 참고 문헌이 필요했다.[7] 소련에서의 진전은 1975년부터 시작된 일련의 서적들에 주로 기술되었다.[8]

Calma의 Graphic Design System(GDS, 1971)과 32비트 후속작인 GDSII(1978)를 통해 엔지니어는 미니컴퓨터에서 전체 칩 레이아웃을 디지털화하고 편집할 수 있게 되었다. 동반된 GDSII 스트림 파일은 사실상의 마스크 교환 표준이 되었으며 현대 설계 흐름에서도 여전히 인정받고 있다.[9]

다음 시대는 1980년 카버 미드린 콘웨이가 "Introduction to VLSI Systems"를 출판하면서 시작되었으며,[10] 이는 칩 설계의 표준 교과서로 간주된다.[11] 그 결과 설계할 수 있는 칩의 복잡성이 증가했으며, 논리 시뮬레이션을 사용하는 설계 검증 도구에 대한 접근성이 향상되었다. 칩은 제작 전에 설계를 더 철저하게 시뮬레이션할 수 있었기 때문에 배치가 더 쉬워졌고 올바르게 작동할 가능성이 높아졌다. 언어와 도구는 발전했지만, 텍스트 프로그래밍 언어로 원하는 동작을 지정하고 도구가 세부적인 물리적 설계를 도출하도록 하는 이 일반적인 접근 방식은 오늘날 디지털 IC 설계의 기초로 남아 있다.

초기 EDA 도구는 학계에서 제작되었다. 가장 유명한 것 중 하나는 초기 VLSI 시스템을 설계하는 데 사용된 UNIX 유틸리티 세트인 "Berkeley VLSI Tools Tarball"이었다. 회로 복잡성 감소를 담당하는 Espresso heuristic logic minimizer[12] 컴퓨터 지원 설계 플랫폼인 Magic[13] 널리 사용되었다. 또 다른 중요한 발전은 실제 집적 회로를 생산함으로써 학생 칩 설계자를 교육하는 저렴한 방법을 개발한 대학 및 제조사 컨소시엄인 MOSIS의 결성이었다.[14] 기본 개념은 신뢰할 수 있고 저렴하며 상대적으로 기술 수준이 낮은 IC 프로세스를 사용하고 웨이퍼당 많은 수의 프로젝트를 팩킹하여 각 프로젝트의 칩 사본을 여러 개 보존하는 것이었다. 협력 제조사들은 이 프로그램이 자신들의 장기적인 성장에 도움이 된다고 보고 처리된 웨이퍼를 기증하거나 원가에 판매했다.

상업적 탄생

[편집]

1981년은 산업으로서 EDA의 시작을 알린 해였다. 수년 동안 휴렛 팩커드, 텍트로닉스, 인텔과 같은 대규모 전자 회사들은 내부적으로 EDA를 추진해 왔으며, 관리자와 개발자들은 EDA를 비즈니스로 집중하기 위해 이러한 회사에서 독립하기 시작했다. Daisy Systems, 멘토 그래픽스Valid Logic Systems가 이 무렵에 설립되었으며 총칭하여 DMV라고 불렸다. 1981년, 미국 국방부는 하드웨어 기술 언어로 VHDL에 대한 자금 지원을 추가로 시작했다. 몇 년 안에 EDA를 전문으로 하는 회사가 많아졌고, 각 회사는 약간씩 다른 강조점을 두었다.

EDA를 위한 첫 번째 전시회는 1984년 Design Automation Conference에서 열렸으며, 1986년에는 또 다른 대중적인 상위 설계 언어인 베릴로그Gateway Design Automation에 의해 하드웨어 기술 언어로 처음 소개되었다. 이러한 도입 직후 시뮬레이터가 뒤따랐으며, 칩 설계의 직접 시뮬레이션과 실행 가능한 사양을 허용했다. 수년 내에 논리 합성을 수행하기 위한 백엔드가 개발되었다.

현대

[편집]

현재의 디지털 흐름은 매우 모듈화되어 있으며, 프런트엔드는 개별 기술에 관계없이 셀과 유사한 단위의 호출로 컴파일되는 표준화된 설계 설명을 생성한다. 셀은 특정 집적 회로 기술의 활용을 통해 논리 또는 기타 전자 기능을 구현한다. 제조사는 일반적으로 표준 시뮬레이션 도구에 적합한 시뮬레이션 모델과 함께 생산 공정을 위한 구성 요소 라이브러리를 제공한다.

대부분의 아날로그 회로는 여전히 아날로그 설계에 고유한 전문 지식(예: 매칭 개념)이 필요한 수동 방식으로 설계된다.[15] 따라서 아날로그 EDA 도구는 훨씬 더 많은 기능이 필요하고 강하게 상호 작용하며 구성 요소가 일반적으로 덜 이상적이기 때문에 모듈성이 훨씬 떨어진다.

전자 제품용 EDA는 반도체 기술의 지속적인 확장에 따라 그 중요성이 빠르게 증가했다.[16] 일부 사용자는 파운드리(fabs)를 운영하는 사업자이며, 추가적으로 EDA 소프트웨어를 사용하여 들어오는 설계의 제조 준비 상태를 평가하는 설계 서비스 회사가 있다. EDA 도구는 또한 사용자 정의 가능한 집적 회로 설계인 FPGA에 설계 기능을 프로그래밍하는 데 사용된다.

소프트웨어 중점

[편집]

설계

[편집]
Image
회로도 캡처 프로그램

설계 흐름은 주로 다음과 같은 몇 가지 기본 구성 요소로 특징지어진다.

  • High-level synthesis(동작 합성 또는 알고리즘 합성이라고도 함) – 상위 수준 설계 설명(예: C/C++)을 레지스터 전송 수준(RTL)으로 변환하며, 레지스터 간의 상호 작용을 통해 회로를 표현한다.
  • 논리 합성 – RTL 설계 설명(예: 베릴로그 또는 VHDL로 작성됨)을 이산 넷리스트 또는 논리 게이트 표현으로 변환한다.
  • Schematic capture – 표준 셀 디지털, 아날로그, RF용으로 Cadence의 Orcad Capture CIS 및 Proteus의 ISIS 등이 있다.
  • 레이아웃 – 일반적으로 Cadence의 Orcad Layout, Proteus의 ARES와 같은 schematic-driven layout이다.

시뮬레이션

[편집]
Image
작은 표준 셀 금속 상호 연결에서 관찰되는 시뮬레이션된 리소그래피 및 기타 제조 결함
  • 트랜지스터 시뮬레이션 – 회로도/레이아웃 동작의 저수준 트랜지스터 시뮬레이션으로 소자 수준에서 정확하다.
  • 논리 시뮬레이션RTL 또는 게이트 넷리스트의 디지털( 0/1) 동작에 대한 디지털 시뮬레이션으로 불 수준에서 정확하다.
  • 동작 시뮬레이션 – 설계 아키텍처 작동의 상위 수준 시뮬레이션으로 사이클 수준 또는 인터페이스 수준에서 정확하다.
  • 하드웨어 에뮬레이션 – 제안된 설계의 논리를 에뮬레이트하기 위해 특수 목적 하드웨어를 사용한다. 때로는 아직 제작되지 않은 칩 대신 시스템에 연결할 수 있는데, 이를 인 서킷 에뮬레이션이라고 한다.
  • Technology CAD – 기본 공정 기술을 시뮬레이션하고 분석한다. 장치의 전기적 특성은 장치 물리학에서 직접 도출된다.

분석 및 검증

[편집]
  • 기능 검증: 논리 설계가 사양과 일치하고 작업을 올바르게 수행하는지 확인한다. 시뮬레이션, 에뮬레이션 및 프로토타입을 통한 동적 기능 검증이 포함된다.[17]
  • 구문, 의미 및 스타일과 같은 코딩 규칙 준수를 위한 RTL 린팅(Linting).[18]
  • 클록 도메인 교차 검증(CDC check): 린팅과 유사하지만, 설계에서 다중 클록 도메인 사용으로 인한 데이터 손실, 메타 스테이빌리티와 같은 잠재적 문제를 감지하고 보고하는 데 특화되어 있다.
  • 형식 검증 또는 모델 체킹: 수학적 방법을 통해 시스템에 특정한 바람직한 속성이 있음을 증명하고, 일부 원치 않는 효과(예: 교착 상태)가 발생할 수 없음을 증명하려 시도한다.
  • 형식 동등성 검사: 칩의 RTL 설명과 합성된 게이트 넷리스트 사이의 알고리즘 비교를 통해 논리적 수준에서 기능적 동등성을 보장한다.
  • 정적 타이밍 분석: 입력에 무관한 방식으로 회로의 타이밍을 분석하여 가능한 모든 입력에 대한 최악의 경우를 찾는다.
  • 레이아웃 추출: 제안된 레이아웃에서 시작하여 모든 배선 및 장치의 (대략적인) 전기적 특성을 계산한다. 완성된 칩의 성능을 추정하기 위해 위의 정적 타이밍 분석과 함께 자주 사용된다.
  • 전자기장 해석기 또는 해석기: IC 및 PCB 설계에서 관심 있는 사례에 대해 맥스웰 방정식을 직접 푼다. 위의 레이아웃 추출보다 느리지만 더 정확한 것으로 알려져 있다.
  • 물리적 검증(PV): 설계가 물리적으로 제조 가능한지, 결과 칩에 기능을 방해하는 물리적 결함이 없는지, 원래 사양을 충족하는지 확인한다.
  • 수율 분석: 제조된 칩의 수율(및 그에 따른 비용)을 추정하고, 유익한 변경을 제안하기 위해 수율 병목 현상을 식별한다.

제조 준비

[편집]
  • 마스크 데이터 준비 또는 MDP - 칩을 물리적으로 제조하는 데 사용되는 실제 포토리소그래피 포토마스크를 생성한다.
    • 레이아웃의 제조 고려 설계(DFM)를 개선하기 위해 맞춤형 명칭 및 구조를 포함하는 칩 피니싱. 후자의 예로는 실 링(seal ring) 및 필러 구조가 있다.[19]
    • 테스트 패턴 및 정렬 마크가 있는 레티클 레이아웃 제작.
    • 그래픽 작업을 통해 레이아웃 데이터를 향상시키는 레이아웃-투-마스크 준비. 예를 들어 최종 포토마스크의 품질을 높이는 방법인 해상도 향상 기술(RET)이 있다. 여기에는 마스크를 사용하여 칩을 제조할 때 나중에 발생하는 회절간섭 효과에 대한 선제적 보상인 광학 근접 교정(OPC) 또는 역 리소그래피 기술(ILT)도 포함된다.
    • 마스크 생성 – 계층적 설계에서 평면 마스크 이미지를 생성한다.
    • 자동 시험 패턴 생성 또는 ATPG – 가능한 한 많은 논리 게이트 및 기타 구성 요소를 실행하기 위해 체계적으로 패턴 데이터를 생성한다.
    • 내장 자체시험 또는 BIST – 설계의 논리 또는 메모리 구조를 자동으로 테스트하기 위해 독립형 테스트 컨트롤러를 설치한다.

기능 안전

[편집]
  • 기능 안전 분석: 원하는 안전 무결성 수준에 대한 준수 요구 사항을 충족하기 위해 설계에 대한 고장률(FIT) 및 진단 범위 지표의 체계적인 계산.
  • 기능 안전 합성: 결함 감지 / 결함 허용 범위를 개선하기 위해 구조화된 요소(모듈, RAM, ROM, 레지스터 파일, FIFO)에 신뢰성 향상을 추가한다. 여기에는 오류 감지 및 수정 코드(해밍), 결함 감지 및 결함 허용을 위한 중복 논리(이중/삼중) 및 프로토콜 검사(인터페이스 패리티, 주소 정렬, 비트 카운트) 등이 포함된다.
  • 기능 안전 검증: 설계에 결함을 삽입하고 안전 메커니즘이 커버되는 것으로 간주되는 결함에 대해 적절한 방식으로 반응하는지 확인하는 것을 포함한 결함 캠페인 실행.
Image
커넥터 설계를 위한 PCB 레이아웃 및 회로도

회사

[편집]

현재

[편집]

2025년 6월 기준 시가총액 및 회사 이름:

시높시스는 2024년에 앤시스 인수를 계획한다고 발표했으나, 앤시스는 거래가 완료될 때까지(2025년 상반기 예상) 독립적인 상장 기업으로 남아 있다.[26]

폐업 또는 인수됨

[편집]

2011년 12월 기준 기준 시가총액 및 회사 이름:[27]

인수 합병

[편집]

많은 EDA 회사들이 핵심 비즈니스에 적합한 소프트웨어나 기타 기술을 보유한 소규모 회사를 인수한다.[32] 대부분의 시장 리더들은 많은 소규모 회사의 합병체이며, 이러한 추세는 디지털 회로에서 대형 벤더의 프로그램 스위트에 자연스럽게 맞는 액세서리로 도구를 설계하려는 소프트웨어 회사의 경향에 의해 촉진된다. 많은 새로운 도구들이 아날로그 설계와 혼합 시스템을 통합하고 있다.[33] 이는 전체 전자 시스템을 단일 칩에 배치하려는 경향 때문에 발생하고 있다.

기계 학습 및 인공지능 기술

[편집]

기계 학습 방법은 이제 상위 수준 합성부터 사인오프(sign-off)에 이르기까지 집적 회로 설계 흐름의 모든 주요 단계에 적용된다. 기계 학습은 소요 시간을 단축하고 전력, 성능 및 면적(PPA)을 개선한다.[34] EDA 벤더들은 이후 유사한 최적화 엔진을 생산 툴체인에 통합했다.[35]

오픈 소스 EDA 생태계의 성장

[편집]

DARPA의 IDEA 프로그램에 따라 시작된 OpenROAD Project(Foundations and Realisation of Open, Accessible Design)는[36] 인간의 개입이 없는(no-human-in-the-loop) RTL-to-GDS 흐름을 출시했으며, 이를 통해 설계를 성공적으로 테이프 아웃했다.[37][38] ORConf 및 연례 FOSSi Foundation 로드맵 세션과 같은 컨퍼런스에서는 이제 오픈 소스 EDA 발전에 상당한 트랙을 할애하고 있다.[39][40]

기술 컨퍼런스

[편집]

같이 보기

[편집]

각주

[편집]
  1. About the EDA Industry. Electronic Design Automation Consortium. August 2, 2015에 원본 문서에서 보존된 문서. July 29, 2015에 확인함.
  2. 1 2 1966: Computer Aided Design Tools Developed for ICs. Computer History Museum. 2023년 1월 1일에 확인함.
  3. Emerson, Roger (2015). The Legendary IBM 1401 Data Processing System. Proceedings of the IEEE 103. 2250–2254쪽. doi:10.1109/JPROC.2015.2480703 (년 이후로 접속 불가 2025-09-24).
  4. Krull, F. N. (1994). The Origin of Computer Graphics within General Motors. IEEE Annals of the History of Computing 16. 40쪽. doi:10.1109/MAHC.1994.298419. S2CID 17776315.
  5. 1 2 EDA (Electronic Design Automation) - Where Electronics Begins. Embed Journal. 2013년 5월 25일. 2023년 1월 1일에 확인함.
  6. TSMC Unveils Industry's First Integrated System-on-Wafer (TSMC-SoW™). TSMC Newsroom. 2023년 4월 26일. 2025년 6월 21일에 확인함.
  7. Vancleemput, W. M. (1973). Automated Design of Digital Systems, A bibliography. University of Waterloo, Dept. of Applied Analysis and Computer Science.
  8. Howard Baldwin (November 2005). From the Ukraine with love. Electronic Business Magazine 31. 22–23쪽.
  9. GDS II User's Operating Manual (PDF). Bitsavers. Calma Company. November 1978. 2025년 6월 21일에 확인함.
  10. Meade, Carver; Conway, Lynn. Introduction to VLSI Design. Addison-Wesley.
  11. Carver Mead Awarded Kyoto Prize by Inamori Foundation. Caltech. 2022년 6월 17일. 2023년 1월 1일에 확인함.
  12. Brayton, Robert K., Gary D. Hachtel, Curt McMullen, and Alberto Sangiovanni-Vincentelli (1984). Logic minimization algorithms for VLSI synthesis 2. Springer Science & Business Media.
  13. Ousterhout, John K., Gordon T. Hamachi, Robert N. Mayo, Walter S. Scott, and George S. Taylor (1985). The magic VLSI layout system. IEEE Design & Test of Computers 2. 19–30쪽. Bibcode:1985IDTC....2...19O. doi:10.1109/MDT.1985.294681.
  14. Tomovich, Christine (1988). MOSIS-A gateway to silicon. IEEE Circuits and Devices Magazine 4. 22–23쪽. Bibcode:1988ICD.....4b..22T. doi:10.1109/101.936.
  15. J. Lienig, J. Scheible (2020). Chap. 6: Special Layout Techniques for Analog IC Design. Fundamentals of Layout Design for Electronic Circuits. Springer. 213–256쪽. doi:10.1007/978-3-030-39284-0. ISBN 978-3-030-39284-0. S2CID 215840278.
  16. Lavagno, Martin, and Scheffer (2006). Electronic Design Automation For Integrated Circuits Handbook. Taylor and Francis. ISBN 0849330963.
  17. Functional Verification. Semiconductor Engineering. 2017년 3월 17일. 2023년 4월 10일에 확인함.
  18. BTV RTL Linting. Retrieved January 2, 2023
  19. J. Lienig, J. Scheible (2020). Chap. 3.3: Mask Data: Layout Post Processing. Fundamentals of Layout Design for Electronic Circuits. Springer. 102–110쪽. doi:10.1007/978-3-030-39284-0. ISBN 978-3-030-39284-0. S2CID 215840278.
  20. Synopsys (SNPS) Market Capitalization. CompaniesMarketCap.com. 2025년 6월 21일에 확인함.
  21. Cadence Design Systems (CDNS) Market Capitalization. CompaniesMarketCap.com. 2025년 6월 21일에 확인함.
  22. ANSS Stock Price & Market Cap. Yahoo Finance. 2025년 6월 21일에 확인함.
  23. Altium (ALU) Overview. Market Index Australia. 2025년 6월 21일에 확인함.
  24. Siemens AG Market Capitalization. StockAnalysis.com. 2025년 6월 21일에 확인함.
  25. Zuken Inc. (6947.T) Stock Price & Market Cap. Yahoo Finance. 2025년 6월 21일에 확인함.
  26. Synopsys to Acquire Ansys, Creating a Leader in Silicon to Systems Design Solutions. Synopsys Newsroom. 2024년 1월 16일. 2025년 6월 21일에 확인함.
  27. Company Comparison - Google Finance. Google.com. Retrieved on 2013-08-10.
  28. Siemens acquires Mentor Graphics for $4.5 billion, eyes connected device, building expansion (영어). ZDNET. 2023년 3월 23일에 확인함.
  29. Dahad, Nitin (2020년 12월 15일). Mentor Finally Becomes Siemens EDA From January 2021. EE Times. 2023년 3월 23일에 확인함.
  30. Dylan McGrath (2011년 11월 30일). Synopsys to buy Magma for $507 million. EETimes. 2012년 10월 25일에 원본 문서에서 보존된 문서. 2012년 7월 17일에 확인함.
  31. Synopsys to Acquire Magma Design Automation.
  32. Kirti Sikri Desai (2006). EDA Innovation through Merger and Acquisitions. EDA Cafe. 2010년 3월 23일에 확인함.
  33. Semi Wiki:EDA Mergers and Acquisitions Wiki (영어). SemiWiki.com. 2011년 1월 16일. 2019년 4월 3일에 원본 문서에서 보존된 문서. 2019년 4월 3일에 확인함.
  34. Huang, Guyue; Hu, Jingbo; He, Yifan; Liu, Jialong; Ma, Mingyuan; Shen, Zhaoyang; Wu, Juejian; Xu, Yuanfan; Zhang, Hengrui; Zhong, Kai; Ning, Xuefei; Ma, Yuzhe; Yang, Haoyu; Yu, Bei; Yang, Huazhong; Wang, Yu (2021년 6월 5일). Machine Learning for Electronic Design Automation: A Survey. ACM Transactions on Design Automation of Electronic Systems 26. 1–46쪽. doi:10.1145/3451179.
  35. Synopsys, Cadence, Google And NVIDIA All Agree: Use AI To Help Design Chips. Forbes.
  36. IDEA: Intelligent Design of Electronic Assets.
  37. Open-Source Semiconductor Chip Design Tool Celebrates Success. UC San Diego News Center. 2022년 2월 24일. 2025년 6월 21일에 확인함.
  38. The OpenROAD Project. The OpenROAD Project. 2025년 6월 21일에 확인함.
  39. ORConf 2024. FOSSi Foundation. 2025년 6월 21일에 확인함.
  40. 2024 Roadmap: Open Source Silicon. FOSSi Foundation Blog. 2024년 8월 16일. 2025년 6월 21일에 확인함.
참고 자료
  • http://www.staticfreesoft.com/documentsTextbook.html Computer Aids for VLSI Design by Steven M. Rubin
  • Fundamentals of Layout Design for Electronic Circuits, by Lienig, Scheible, Springer, doi:10.1007/978-3-030-39284-0ISBN 978-3-030-39284-0, 2020
  • VLSI Physical Design: From Graph Partitioning to Timing Closure, by Kahng, Lienig, Markov and Hu, doi:10.1007/978-3-030-96415-3ISBN 978-3-030-96414-6, 2022
  • Electronic Design Automation For Integrated Circuits Handbook, by Lavagno, Martin, and Scheffer, ISBN 0-8493-3096-3, 2006
  • The Electronic Design Automation Handbook, by Dirk Jansen et al., Kluwer Academic Publishers, ISBN 1-4020-7502-2, 2003, available also in German ISBN 3-446-21288-4 (2005)
  • Combinatorial Algorithms for Integrated Circuit Layout, by Thomas Lengauer, ISBN 3-519-02110-2, Teubner Verlag, 1997.