:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.24 No.2 | (2024) pp.105~111
격자 그래프의 최소선형배열 알고리즘
Abstract
격자 그래프의 최소 선형 배열(MinLA)은 선형 복잡도 O(n) 의 근사 알고리즘이 적용되고 있으며, 33×33격자의 최적 MinLA는 31,680으로 알려져 있다. 본 논문은 격자의 정확한 해 MinLA를 복잡도 O(1)으로 구하는 분할배열 알고리즘을 제안하였다. 분할배열 알고리즘은 컨테이너에 박스를 넣는 방법으로 m행을 r1, r2, r3로, n열을 c1, c2, c3로 분할하여 7개 컨테이너를 얻고 규칙을 가지도록 분할한다. 분할된 박스들에 있는 정점들 위치 순서로 번호를 부여하여 MinLA를 구한다. m,n ≥ 11에 대해 C2, C4, C6박스 크기를 2씩 증가시키면서 MinLA가 증가할 때까지 반복 수행한다. 이 과정은 에 대해 최대 4회 반복 수행하는 특징이 있다. 제안된 알고리즘은 m=n과 m≠n인 모든 격자에 적용할 수 있다. 분할배열 알고리즘을 2≤n≤100 격자에 적용하였으며, 33×33과 100×100격자에 대해 기존 알고리즘들보다 월등히 좋은 최적의 결과를 얻었다. 제안된 알고리즘은 간단하면서도 보다 정확한 해를 얻을 수 있어 m,n이 무한히 크더라도 쉽게 해를 얻을 수 있어 VLSI 회로 설계 분야에 응용이 될 수 있을 것이다.
This paper deals with the minimum linear arrangement(MinLA) of a lattice graph, to which an approximate algorithm of linear complexity O(n) remains as a viable solution, deriving the optimal MinLA of 31,680 for 33×33 lattice. This paper proposes a partitioning arrangement algorithm of complexity O(1) that delivers exact solution to the minimum linear arrangement. The proposed partitioning arrangement algorithm could be seen as loading boxes into a container. It firstly partitions m rows into r1, r2, r3 and n columns into c1, c2, c3 , only to obtain 7 containers. Containers are partitioning with a rule. It finally assigns numbers to vertices in each of the partitioned boxes location-wise so as to obtain the MinLA. Given m,n ≥ 11, the size of boxes C2, C4, C6 is increased by 2 until an increase in the MinLA is detected. This process repeats itself 4 times at maximum given m,n ≤ 100. When tested to lattice in the range of 2 ≤ n ≤ 100, the proposed algorithm has proved its universal applicability to lattices of both m=n and m≠n. It has also obtained optimal results for 33×33 and 100×100 lattices superior to those obtained by existing algorithms. The minimum linear arrangement algorithm proposed in this paper, with its simplicity and outstanding performance, could therefore be also applied to the field of Very Large Scale Integration circuit where m,n are infinitely large.
Minimum linear arrangement,Optimal linear ordering,Layout problem,Lattice,Mesh
