라우팅(전자 설계 자동화)

Routing (electronic design automation)
이 기사는 전자 설계 자동화의 일환으로 집적회로를 설계하는 것에 관한 것입니다.그 외의 라우팅의 종류에 대해서는, 「루팅」을 참조해 주세요.

전자 설계에서 와이어 라우팅은 일반적으로 단순 라우팅이라고 불리며 프린트 회로 기판(PCB) 및 집적 회로(IC) 설계의 한 단계입니다.이것은 배치라고 불리는 선행 단계를 기반으로 구축됩니다.이것은 PCB 상의 IC 또는 컴포넌트의 각 활성 요소의 위치를 결정합니다.배치 후 라우팅 스텝은 IC의 모든 설계 규칙을 준수하면서 배치된 컴포넌트를 올바르게 연결하기 위해 필요한 와이어를 추가합니다.IC 설계의 배치 단계와 라우팅 단계를 함께 장소와 경로라고 합니다.

모든 라우터의 작업은 동일합니다.셀의 핀(단자라고도 함)으로 구성된 기존 폴리곤과 선택적으로 프리루트라고 하는 기존 배선이 제공됩니다.이러한 폴리곤 각각은, 통상, 이름이나 번호에 의해서 그물망과 관련지어집니다.라우터의 주요 태스크는 같은 네트워크에 할당된 모든 단말기가 접속되고 다른 네트워크에 할당된 단말기가 접속되지 않으며 모든 설계 규칙을 따르도록 지오메트리를 작성하는 것입니다.라우터는 접속할 필요가 있는 단말기를 접속하지 않거나(오픈), 접속할 필요가 없는2대의 단말기를 잘못 접속하거나(쇼트), 설계규칙 위반을 생성함으로써 장애가 발생할 수 있습니다.또, 그물을 올바르게 접속하기 위해서, 라우터는 설계가 타이밍에 적합하고, 크로스 토크에 문제가 없고, 금속 밀도 요건을 충족하고, 안테나의 영향을 받지 않는 것을 확인할 수도 있습니다.종종 모순되는 목표의 긴 목록이 루팅을 매우 어렵게 만드는 이유입니다.

라우팅과 관련된 거의 모든 문제는 다루기 어려운 것으로 알려져 있습니다.Steiner 트리 문제라고 불리는 가장 간단한 라우팅 문제는 장애물이 없고 설계 규칙도 없는 1개의 레이어 내에서 1개의 네트에 대한 최단 루트를 찾는 것입니다.모든 각도가 허용되면 NP-hard이고 수평 및 수직 와이어만 허용되면 NP-complete입니다.채널 라우팅의 바리안트는 NP-complete이며 크로스톡이나 via의 수 등을 줄이는 라우팅도 있습니다.따라서 라우터는 최적의 결과를 찾으려고 거의 시도하지 않습니다.대신, 거의 모든 라우팅은 충분한 해결책을 찾으려고 하는 휴리스틱에 기초하고 있습니다.

설계 규칙은 레이어마다 상당히 다를 수 있습니다.예를 들어 하층에서의 허용 폭 및 간격은 상층에서의 허용 폭 및 간격보다 4배 이상 작을 수 있다.이것에 의해, 프린트 기판이나 멀티 칩모듈 설계등의 다른 애플리케이션에서는 라우터가 직면하지 않는 많은 복잡성이 발생합니다.규칙이 서로 단순한 배수가 아닌 경우, 그리고 다른 규칙을 가진 계층 사이를 이동해야 할 때 특정한 어려움이 뒤따른다.

라우터의 종류

PCB는 컴퓨터 디자인(왼쪽)으로 컴포넌트로 채워진 보드 어셈블리로 구현됩니다(오른쪽).보드는 양면이며 관통 구멍 도금, 녹색 솔더 레지스트 및 흰색 범례입니다.표면 마운트 및 관통 구멍 구성 요소가 모두 사용되었습니다.

EDA 라우터의 초기 타입은 「수동 라우터」로, 드래프트는 각 네트워크의 각 회선 세그먼트의 엔드 포인트에서 마우스를 클릭했습니다.최신 PCB 설계 소프트웨어는 일반적으로 "인터랙티브 라우터"를 제공합니다.드래프트는 패드를 선택하고 몇 군데를 클릭하여 EDA 툴이 어디로 가야 할지 알 수 있도록 합니다.EDA 툴은 설계 규칙 체크(DRC)를 위반하지 않고 가능한 한 그 경로에 와이어를 배치하려고 합니다.보다 고도의 인터랙티브라우터 중에는 인터랙티브라우터에 「밀어서 밀어넣기」기능(「밀어서 밀어넣기」또는 「자동화」기능)이 있는 것도 있습니다.EDA 툴은 가능하면 다른 네트워크를 밀어내어 드래프트가 원하는 장소에 새로운 와이어를 배치하고 DRC를 위반하지 않도록 합니다.최신 PCB 설계 소프트웨어에서는 일반적으로 사용자의 개입 없이 나머지 모든 라우팅되지 않은 연결을 라우팅하는 "오토라우터"도 제공됩니다.

자동 라우터의 주요 유형은 다음과 같습니다.

라우터의 구조

많은 라우터가 다음 알고리즘 전체를 실행하고 있습니다.

  • 우선, 각 넷의 대략적인 코스를 결정합니다(대부분의 경우 거친 그리드로 라우팅합니다).이 스텝은 글로벌라우팅이라고 [19]불리며 옵션으로 레이어 할당을 포함할 수 있습니다.글로벌 라우팅은 다음과 같은 상세한 라우팅 스텝의 크기와 복잡성을 제한합니다.이러한 라우팅 스텝은 그리드별로 정사각형으로 실행할 수 있습니다.

자세한 라우팅에서는 가장 일반적인 방법은 리핑 및 리핑과 [1]재루팅입니다.

  • 넷이 라우팅 되는 순서를 선택합니다.
  • 각 네트워크를 순서대로 라우팅합니다.
  • 모든 네트가 정상적으로 라우팅되지 않을 경우 선택한 루팅을 삭제하고 나머지 넷의 라우팅 순서를 변경하여 나머지 루팅을 재시도하는 다양한 '클린업' 방식을 적용합니다.

이 프로세스는 모든 네트가 라우팅되거나 프로그램(또는 사용자)이 포기될 때까지 반복됩니다.

대체 접근법은 단락, 설계 규칙 위반, 장애물 등을 초과 와이어 길이로 유사한 기반에서, 즉 피해야 할 절대적인 비용이 아닌 (처음에는) 유한한 비용으로 처리하는 것입니다.이 멀티패스 라우팅 방식은 다음 알고리즘에 의해[20] 설명됩니다.

  • 여러 번의 반복 패스에 대해 다음 절차를 수행합니다.
  • "객관적 기능"의 무게 매개 변수를 규정 또는 조정합니다(과잉 와이어 길이의 각 단위 및 위반 유형에 대한 무게 매개 변수 값이 있음).예를 들어, 첫 번째 패스의 경우, 과도한 와이어 길이는 일반적으로 높은 비용이 드는 반면, 쇼트나 인접 등의 설계 위반은 낮은 비용이 됩니다.나중에는 위반이 비용이 많이 들거나 완전히 금지될 수 있도록 비용의 상대적 순서가 변경됩니다.
  • 이 패스중에 넷을 라우팅 하는 순서를 선택합니다(또는 랜덤으로 선택합니다).
  • 「Rip up」(이전에 라우팅 된 경우)과 각 넷의 루팅을 차례로 실시해, 그 넷의 목적 함수의 값을 최소한으로 억제합니다(일반적으로 라우팅의 일부에는 쇼트나 다른 설계 위반이 있습니다).
  • 라우팅이 완료되어 올바르거나 더 이상 개선되지 않거나 기타 종료 기준이 충족될 때까지 다음 반복 패스로 진행합니다.

대부분의 라우터는 주로 "x" 또는 "y" 방향 배선을 반송하기 위해 배선 레이어를 할당합니다.다만, 이러한 [21]할당의 필요성을 회피하거나 줄이는 라우터가 있었습니다.각 접근법에는 장점과 단점이 있습니다.방향이 제한되어 있기 때문에 전원장치 설계와 레이어 간 크로스톡 제어가 쉬워지지만 임의의 루트를 허용하면 비아의 필요성을 줄이고 필요한 배선층의 수를 줄일 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e Byers, T. J. (1991-08-01). Printed Circuit Board Design with Microcomputers (1 ed.). New York, USA: Intertext Publications/Multiscience Press, Inc., McGraw-Hill Book Company. pp. 99–101. ISBN 978-0-07-009558-8. LCCN 91-72187.
  2. ^ Ritchey, Lee W. (December 1999). "PCB routers and routing methods" (PDF). PC Design Magazine. Speeding Edge (February 1999). Archived (PDF) from the original on 2018-10-22. Retrieved 2018-10-22.
  3. ^ Lee, Chester Y. (September 1961). "An algorithm for path connections and its applications". IRE Transactions on Electronic Computers. EC-10 (3): 346–365. doi:10.1109/TEC.1961.5219222. S2CID 40700386.
  4. ^ a b c d e Kollipara, Ravindranath; Tripathi, Vijai K.; Sergent, Jerry E.; Blackwell, Glenn R.; White, Donald; Staszak, Zbigniew J. (2005). "11.1.3 Packaging Electronic Systems - Design of Printed Wiring Boards" (PDF). In Whitaker, Jerry C.; Dorf, Richard C. (eds.). The Electronics Handbook (2 ed.). CRC Press, Taylor & Francis Group, LLC. p. 1266. ISBN 978-0-8493-1889-4. LCCN 2004057106. Archived (PDF) from the original on 2017-09-25. Retrieved 2017-09-25.
  5. ^ Hadlock, Frank O. (1977-12-01). "A shortest path algorithm for grid graphs". Networks. 7 (4): 323–334. doi:10.1002/net.3230070404.
  6. ^ Mikami, Koichi; Tabuchi, Kinya (1968). A computer program for optimal routing of printed circuit connectors. IFIPS Proceedings. Vol. H47. pp. 1745–1478.
  7. ^ Hightower, David W. (1969). "A solution to line-routing problems on the continuous plane". DAC'69: Proceedings of the 6th Annual Conference on Design Automation. ACM Press. pp. 1–24. {{cite conference}}: 외부 링크 입력(도움말)(NB).여기에는 '라인 프로브 라우터'의 첫 번째 설명 중 하나가 포함됩니다).
  8. ^ a b c d Minges, Merrill L. (1989). Electronic Materials Handbook: Packaging. Vol. 1. ASM International. ISBN 978-0-87170-285-2. Retrieved 2017-09-27.
  9. ^ Reed, James B.; Sangiovanni-Vincentelli, Alberto; Santamauro, Mauro (1985). "A new symbolic channel router: YACR2". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 4 (3): 203–219. doi:10.1109/TCAD.1985.1270117. S2CID 17065773. [1]
  10. ^ a b c Shankar, Ravi; Fernandez, Eduardo B. (2014-01-12). Einspruch, Norman G. (ed.). VLSI and Computer Architecture. VLSI Electronics Microstructure Science. Vol. 20. Academic Press. ISBN 978-1-48321784-0. Retrieved 2018-10-22.
  11. ^ McLellan, Paul (2012-04-23). "Channel Routing Memories". Archived from the original on 2021-05-18. Retrieved 2022-01-01.
  12. ^ Finch, Alan C.; Mackenzie, Ken J.; Balsdon, G. J.; Symonds, G. (1985-06-23). A Method for Gridless Routing of Printed Circuit Boards (PDF). 22nd ACM/IEEE Design Automation Conference, Las Vegas, Nevada, USA. Design Automation Conference, 2009. Dac '09. 46Th Acm/IEEE. Newtown, Tewkesbury, Gloucestershire, UK: Racal-Redac Ltd. pp. 509–515. doi:10.1109/DAC.1985.1585990. ISBN 0-8186-0635-5. ISSN 0738-100X. Archived (PDF) from the original on 2018-10-22. Retrieved 2018-10-22.
  13. ^ Webb, Darrell (2012-12-20). "A Tribute to Alan Finch, the Father of Gridless Autorouting". Archived from the original on 2018-10-22. Retrieved 2018-10-22.
  14. ^ Wu, Bo (April 1992). Graph Theory Based Routing Algorithms (PDF) (Thesis). Western Michigan University. S2CID 3357923. Archived from the original (PDF) on 2018-10-22. Retrieved 2018-10-22.
  15. ^ "Computer-Partner Kiel GmbH: "Bloodhound" entflechtet Leiterplatten auf 16 Lagen". Computerwoche (in German). 1992-03-13. Archived from the original on 2018-10-21. Retrieved 2018-10-20.
  16. ^ Pfeil, Charles (2017-11-02). "A lifetime designing PCBs: From design to software". EDN Network. Archived from the original on 2018-10-21. Retrieved 2018-10-20.
  17. ^ a b Redlich, Detlef. "1.6. Rechnergestützter Leiterplattenentwurf - Entflechtung" (PDF). Schaltungsdesign (in German). Ernst-Abbe-Hochschule Jena (EAH). Archived from the original (PDF) on 2018-10-21. Retrieved 2018-10-20.
  18. ^ "Simplify Design Automation – the next generation in design methodology".
  19. ^ Soukup, Jirí (1979). "Global Router". Proceedings of the 16th Design Automation Conference. San Diego, CA, USA: IEEE Press. pp. 481–489.
  20. ^ Rubin, Frank (1974). "An iterative technique for printed wire routing". Proceedings 11th Design Automation Workshop. pp. 308–13.
  21. ^ Linsker, Ralph (1984). "An iterative-improvement penalty-function-driven wire routing system" (PDF). IBM Journal of Research and Development. 28 (5): 613–624. doi:10.1147/rd.285.0613.

추가 정보

외부 링크