Interconnection networks equipped with wormhole switching have been widely used for contemporary multicomputers/parallel machines because of its various advantageous features and good performance. The communication performance in wormhole routing networks is no longer sensitive to path lengths and minimizing the lengths is no longer a major concern. However, in wormhole routing, messages must compete for channels, and the resultant contention affects communication times. Thus, a random mapping is still not enough.
In this thesis, we deal with the mapping problem on wormhole routing networks. Not only abstracted and stochastic task models but also more realistic parallel applications are considered. It is difficult to define and evaluate a meaningful performance metric when many messages are generated and exchanged concurrently in large wormhole routing networks. We analyze extensively the blocking characteristics of packets in wormhole routing network based on queuing system model. As a result of the analysis, we formulate a new cost function to evaluate how a mapping have good performance. The cost function reflect the contention property more exactly than others which have been suggested by a lot of researchers. The new cost function helps us to select more accurate and stable mapping with respect to the parameters of parallel tasks and multicomputers such as packet-length and operating network load.
It is known that there is no polynomial time algorithm to find optimal mapping with a given objective function, in general case of mapping. We devise heuristic algorithms to find a near-optimal mapping with respect to the proposed cost function. The algorithms include a greedy algorithm and a heuristic optimization algorithm. The greedy mapping algorithm shows significant performance improvements over random mappings, and it is useful to use as an initial mapping algorithm for a heuristic optimization algorithm. The proposed heuristic optimization algorithm which is based on KL-algorithm can deal with not only one-to-one but also many-to-one mappings.
To evaluate various mapping schemes, we have made extensive experiments through wormhole routed multicomputer simulator, for various types of tasks and various system topologies. The results show that the proposed cost function have good performance over others in most of cases.
여러가지 성능상의 잇점으로 웜홀 라우팅 스위칭을 장착한 상호연결 네트워크는 현대의 다중 혹은 병렬 컴퓨터에서 널리 사용되고 있다. 웜홀 라우팅 네트워크에 있어서의 통신 성능은 더 이상 패스의 길이에 민감하게 영향을 받지 않으므로 그 길이를 최소화 하는 것은 주 관심사가 아니다. 반면에, 웜홀 라우팅에서는 메시지들이 채널을 차지하기 위하여 서로 경쟁하며 결과로 생기는 충돌(contention) 현상이 통신 성능에 지대한 영향을 미친다. 그러므로, 랜덤한 맵핑은 여전히 충분하지 못하며, 기존에 제안된 여러 맵핑 함수는 이러한 웜홀 라우팅 네트웍의 특성을 적절히 반영하지 못하였다.
본 논문에서는 웜홀 라우팅 네트워크를 갖는 다중 컴퓨터에서의 맵핑 문제를 다룬다. 추상화된 병렬 응용 뿐만이 아니라 좀더 실제의 응용 프로그램들이 다루어 진다. 그 특성상의 비 예측성 때문에, 큰 웜홀 라우팅 네트워크에서 정확한 의미의 성능 척도를 정하거나 평가하는 것은 쉽지가 않다. 우리는 본 논문에서 한 큐잉(queuing) 시스템 모델을 가지고 웜홀 라우팅 네트워크에서의 메시지들의 대기(blocking) 특성을 심도있게 분석한다. 그 분석의 결과로, 맵핑의 좋은 정도를 재는 기준이 될 새로운 비용함수(cost function)를 수식화하여 제안한다. 이 비용함수는 기존에 여러 연구가들에 의해 제안된 것들에 비해 웜홀 라우팅 네트워크에 있어서의 충돌 특성을 보다 정확히 반영하고 있다. 또한 메시지 패킷의 크기(L)와 동작하는 네트워크의 로드 등의 시스템의 특성 인자들에 대하여 보다 최적화된 맵핑을 찾을 수 있게 한다.
한 주어진 목적 함수에 대하여 최적화된 맵핑을 폴리노미알(polynomial) 시간에 찾는 것이 불가능한 것으로 알려져 있다. 따라서, 우리는 본 논문에서 제안된 비용 함수에 대하여 최적에 가까운 맵핑을 효율적으로 찾아주는 알고리즘들을 제안한다. 이들은 한 그리디(greedy) 알고리즘과 한 휴리스틱(heuristic) 최적화 알고리즘이다. 그리디 알고리즘은 랜덤 맵핑에 비해 상당한 성능 개선을 보여주는데, 이는 휴리스틱 최적화 알고리즘의 초기화 맵핑으로 사용하는데 적합하다. 제안된 휴리스틱 최적화 알고리즘은 KL-알고리즘을 기반으로 개발되었으며, 일대일 맵핑 뿐만이 아니라 다대일 맵핑에서도 적용될 수 있도록 하였다.
제안된 맵핑 방식의 성능을 평가하기 위하여 다양한 태스크 종류와 다양한 시스템 토폴리지에 대해서 웜홀 라우팅 다중 컴퓨터 시뮬레이터를 통하여 실험을 수행하였다. 패킷의 크기와 네트워크 로드의 효과를 보여주는 실험에서 주어진 이들 값에 최적화하여 얻어진 맵핑들이 대응되는 시스템의 환경에서 보다 나은 성능을 보였다. 그러나, 주어진 대상 로드에 대하여 최적화하여 얻어진 맵핑들이 다른 시스템 로드에서 다른 비용함수로써 얻어진 맵핑들에 비해 나쁜 성능을 보일정도로 그 영향이 그렇게 민감하진 않았다. 결론적으로 0.2 ~ 0.4 범위의 로드에서 얻어진 맵핑들은 태스크의 종류가 어떠하든 간에 좋은 성능을 나타냈다. 이 새로운 맵핑 함수는 일대일 뿐만이 아니라 다대일 맵핑에서도 좋은 성능을 보임을 실험을 통해 알 수 있었다.
