The parallel processing techniques have been widely researched in an effort to improve the performance of processing large and complex operations in both numerical and non-numerical applications. One of the typical approach is the automatic parallelizing compilers which transform sequential programs to parallel programs. However, many scientific operations, such as recurrence operation, are not yet suitably treated by parallel processing because of their intrinsic difficulty of parallelizing and peculiar attributes in their formula despite they are important and widely used. There are several researches on the first-order linear recurrence operation using vector super=computers achieving considerable performance enhancement. In this thesis, we focus on parallelization of recurrence operations in SMP machines. Recently , SMP machines have rapidly been developed and their performance and scalability have shown considerable progress. In the present, SUN and Intel are supplying the server market with various models of SMP machines, such as 4-way, 8-way, and 64-way system. However, there is few work related to parallel processing of scientific computation using SMP machines.
Recurrence operation has typical characteristic which are required in many basic scientific computations. So the research on the parallel processing of recurrence operations in SMP machines can be generally applied to any other scientific and mathematical computations. We have employed various algorithms using thread technique in one-dimensional and two-dimensional recurrence operations on SMP machines. We have evaluated and analyzed the performance results. We have observed reasonable performance enhancement. The memory contention and some problems related to memory architectures predicted in the beginning of the work turned out to be to longer serious problems in the small-scale SMP machines. Cache memory has a great role in the performance of SMP machines even in scientific computations.
병렬처리에 대한 연구는 세계적으로 널리 연구되고 있다. 이러한 경향에 힘입어 자동적으로 순차적프로그램을 병렬화 시켜주는 자동병렬화 컴파일러에 대한 연구도 널리 행해지고 있다. 그러나, 많은 과학계산에서 사용되는 연산들 중 회귀연산과 같은 경우는 그 연산에 내재하고 있는 특이한 속성들로 인하여 많은 분야에서 사용되고는 있지만 병렬화가 용이치 못한 것들이 있다. 1차 회귀연산의 경우는 벡터기반의 슈퍼컴퓨터에서 많은 연구가 행해졌고 이러한 연구를 바탕으로 한 다양한 시도로 인해 일부 성능의 향상을 가져온 경우도 있었다. 본 연구에서는 이러한 연산들 중 회귀연산에 대해 SMP 기반 컴퓨터 상에서의 병렬화에 초점을 맞추었다. SMP 기반의 컴퓨터는 현재 널리 개발이 이루어지고 있으며 성능과 scalability, 또한 가격면에서도 많은 향상을 가져오고 있다. 우리는 기존의 알려진 몇몇 알고리즘에 대해 SMP 에 적합한 방식을 이용해 thread 를 기반하여 1차원과 2차원배열에서의 회귀연산에 대한 병렬화를 개작을 통하여 구현, 실험을 하였다. 이러한 실험의 결과는 만족할 만한 성능의 향상을 가져왔으며 부수적으로 메모리 구조상의 문제로 피할 수 없으리라 여겨지던 memory contention 에 관련한 문제는 적어도 이러한 small-scale SMP 컴퓨터에서는 그리 심각한 문제가 아니었다.
본 연구에서는 Intel CPU에 기반한 4-way와 8-way SMP 머쉰이 주로 구현 및 성능 테스트에 이용이 되었으며, Sun Sparc CPU 를 채용한 4-way 머쉰도 test가 되었다. 주된 구현은 C에서 Solaris 기반의 thread librery를 이용하였으며, 1차원 배열에서의 1차회귀연산과 2차원 배열에서의 1차회귀연산, 그리고 wavefront 방식의 2차회귀연산에 대한 구현과 결과가 연구되었다. 실험 결과는 만족할 만한 성능향상을 가져왔으며, 특히 캐쉬메모리 및 일반 주메모리 접근에 대한 기존의 알려진 여러가지 기술을 적용하였을 때는 상당한 성능향상을 보인 예도 있었다.
1차 회귀연산의 경우 SMP 머쉰에 특화된 알고리즘을 바탕으로 하여 성공적인 병렬화를 거두었으며, 이때 경량 분할을 통하여 캐쉬 메모리를 더욱 효율적으로 이용할 경우 좀더 나은 성능향상이 가능하리라 예상되었다. 또한 2차원 배열에서의 회귀연산의 병렬처리에 사용된 동기화 방법인 spin-lock 방식은 실제로 이러한 회귀연산에 대해서는 그리 큰 부하를 보여주지 않았으며, 생성된 데이타를 분석한 결과 역시 좋은 성능을 보여주고 있었다. 무엇보다 이 방식의 장점은 프로그램에 대한 수정이 wavefront 방식에 비해 훨씬 간결한 반면, 적당한 크기의 수행배열이 할당될 경우 성능에 큰 편차를 보이지 않고 있어 자동 병렬화등에서 충분히 이용될 가능성을 보이고 있다.
지금까지 알려진 SMP 의 특징적인 문제점들은 본 연구에서는 큰 영향을 미치지 않았으며, 향후 발전하는 개별 컴퓨터구조의 요소와 캐쉬메모리의 증가는 이러한 문제점들이 SMP 시스템의 과학 계산용으로서의 사용을 방해하지는 않을 것이란 사실을 확인할 수 있었다.
