Déjà Vu Packing: FPGA 로직 클러스터링 런타임을 패턴 메모이제이션을 통해 최적화하기

FPGA 패브릭에 디지털 회로를 구현하려면 기술 매핑된 네트리스트 (netlist) 프imitives 를 더 거친 수준의 블록으로 클러스터링해야 하며, 이 블록들은 FPGA 의 물리적 리소스에 직접 매핑될 수 있어야 합니다. FPGA 로직 블록 (LBs) 의 아키텍처가 복잡해지면서 정교한 로직 요소 (LEs) 와 매우 불규칙한 지역 인터커넥트를 갖게 되면서, 이 패킹 (packing) 문제는 더 어려워졌습니다. 클러스터 내 라우팅의 실현 가능성을 보장하기 위해 컴퓨터 지원 설계 (CAD) 도구는 각 후보 클러스터에 대해 비용이 많이 드는 다중 소스-다중 싱크 (multi-source multi-sink) 라우팅 문제를 해결해야 합니다. 본 논문에서는 먼저 이러한 패킹 적법성 (legality) 체크가 복잡한 LE 와 현대 상용 FPGA 에 해당하는 지역 라우팅 구조를 갖는 LB 아키텍처의 CAD 플로우 런타임의 상당 부분을 차지함을 보여줍니다. 우리는 다양한 벤치마크를 AMD 7 시리즈 유사 및 Altera Stratix-10 유사 VTR 아키텍처 캡처에 매핑할 때 패킹 단계가 전체 Versatile Place and Route (VPR) 플로우 런타임을 평균적으로 각각 58% 와 94% 를 차지함을 증명합니다. 패킹 알고리즘 동작을 분석한 결과, 시도된 패킹 클러스터 중 상당 부분이 훨씬 적은 수의 패킹 패턴의 반복임을 관찰하였으며, 따라서 많은 패킹 적법성 체크가 중복되어 생략할 수 있음을 발견했습니다. 이 목적을 위해 우리는 Déjà Vu 패킹 접근법을 소개하며, 이는 재귀하는 패킹 패턴을 효율적으로 식별하고 그 적법성 체크 결과를 메모이제이션 (memoization) 할 수 있는 새로운 패킹 서명 트리 (packing signature tree) 데이터 구조를 활용합니다. 우리의 접근법은 평가된 벤치마크에서 7 시리즈 아키텍처와 Stratix 10 아키텍처에 걸쳐 패킹 런타임을 최대 13.4 배 및 29.3 배, 평균적으로 각각 3.7 배 및 6.9 배 가속화합니다. 이러한 패킹 런타임 향상은 결과의 품질을 유지하면서 엔드투엔드 VPR 런타임을 평균적으로 각각 1.6 배 및 5.3 배 크게 줄이는 효과를 가져옵니다.