방향그래프에서 사이클을 찾기 위한 효율적인 병렬알고리즘

본 논문은 방향그래프에서 사이클을 찾는 알고리즘으로 Transitive Closure를 기본구조로 하고 있는 All Pairs Shortest Paths 알고리즘을 주로 사용하여 사이클을 찾을 수 있도록 변형하였다. 또한 이 알고리즘을 2차원 시스톨릭 배열에서 구현하면 O(N²)이지만, 본 논문에서는 매우 큰 크기의 방향그래프를 기존의 작은 용량(m)의 VLSI 구조에 맞추어 분할하여 3차원 Mesh of Tree에서 구현하여 속도를 향상시켰다. 이 분할 맵핑 방법을 사용하지 않고 3차원 Mesh of Tree에서 구현할 경우의 속도는 O(NlogN)이지만, 분할 맵핑 방법을 적응할 경우 그 속도는 O( (N/m)log(N/m)) 이 된다.