오늘날 과학과 공학 분야의 문제들은 많은 자료 처리와 빠른 계산을 요구하고 있다. 이를 위해 기존의 컴퓨터 보다 더욱 빠른 계산 능력을 갖는 고성능 컴퓨터에 대한 요구는 증가하고 있다. 컴퓨터 성능 향상을 위한 방법으로 병렬 처리(parallel processing) 기술이 널리 사용되고 있다. 병렬 처리란 다수의 프로세서들이 여러 개의 프로그램 또는 한 프로그램의 분할된 부분들을 분담하여 동시에 처리하는 기술을 말한다.
병렬 처리 분야에서 응용되는 상호연결망은 활용 분야와 목적에 따라 다양하게 제안되었다. 상호연결망(interconnection network)은 컴퓨터 시스템의 프로세서(processor)를 연결하는 구조를 나타낸 것으로 전체 시스템의 성능(performance)에 영향을 미치는 중요한 요소 중 하나이다.
상호연결망을 평가하는 척도 중 한 가지로 망비용(network cost)이 있다. 망비용(network cost)은 분지수(degree) × 지름(diameter)으로 정의된다. 지금까지 제안된 상호연결망으로 메쉬(mesh), 하이퍼큐브(hypercube), 스타(star) 그래프가 있다. 하이퍼큐브 연결망은 각종 응용 분야에서 요구하는 통신망 구조(network structure)를 쉽게 제공할 수 있는 장점이 있어서 상용 시스템(commercial system)으로 개발되어 활용되고 있다. 하이퍼큐브의 망비용은 O(n²)을 갖는다.
본 연구에서는 하이퍼큐브 부류의 망비용을 개선하기 위해 새로운 로그-하이퍼큐브 그래프(Log-hypercube graph)를 제안하고 라우팅 알고리즘(routing algorithm)을 개발하였다. 로그-하이퍼큐브에서 망비용을 개선한 방법은 분지수(degree)의 개수를 O(log₂n)이 되도록 하였다. 동일한 노드 개수를 갖는 하이퍼큐브 그래프의 분지수 O(n)이다.
로그-하이퍼큐브의 재귀적 분할(recursive partition) 성질을 이용한 라우팅 알고리즘(routing algorithm)의 지름(diameter)은 1.5n-1이다. 또한 로그-하이퍼큐브의 확장성(scalability), 연결도(connectivity), 고장 허용도(fault tolerance)의 성질을 분석하였다.
본 논문에서 제시한 로그-하이퍼큐브를 동일한 노드수를 가진 하이퍼큐브 부류의 상호연결망과 비교하면 망비용 관점에서 O(n²)에서 O(nlog₂n)으로 개선된 결과를 갖는다.