Computer systems with multiple processors are developed to solve the computation heavy applications effectively. Many commercial processors support multiprocessor systems in the symmetric multi processing(SMP) form. SMP is one of the shared memory multiprocessor systems which provide shared memory programming environment, and have a problem of limited scalability. To solve the scalability problem without changing programming environment too much, distributed shared memory(DSM) systems are invented. But, DSMs suffer its large remote memory access delays, and reducing the effect of the large delay have become a main design issue of DSMs.
Modern processors use various mechanisms of instruction level parallelism(ILP) to extract maximum performance within the physically limited clock speed. The ILP mechanisms are based on speculations and out-of-order executions. So, using the ILP on a shared memory multiprocessor system may cause memory inconsistency and can pro-duce incorrect results. Without the ILP, the performance of the shared memory multiprocessor system will be too poor. And the ILP can also hide the large remote memory access delay of DSMs. Most processors which support both SMP and ILP have special instructions which control memory access ordering by stalling pipeline until desired conditions are met.
With its large remote memory access delay, DSMs also have different memory access characteristics over SMP. SMP systems use the cache coherence uniform memory access(CC-UMA) scheme and have monolithic memory architecture, so all the memory areas are shared and identical to the all processors. But, DSMs use the cache coherence non uniform memory access(CC-NUMA)scheme and have two different memory types, one is a private memory which is located at the same node with each processor and other processor cannot access it directly, another is a shared memory which is shared by all the processors and may be located on another node. So, the shared memory access may have the large remote memory access delay. The difference makes the shared memory multi processor support mechanisms in SMP processors being not sufficient in DSMs, and different approachs are proposed by many researchers.
Those approaches are based on increasing ILP to hide large remote memory access delay with useful computations. Ranganathan et al.,[9] suggested the speculative retirement(SR) of load instructions and the SR scheme uses a history buffer to store speculatively retired instructions. Gniady et al.,[10] designed the SC++ scheme to execute and retire store instructions speculatively in addition to the SR scheme. SC++ uses Speculative History Queue(SHiQ) to store speculatively retired instructions along with original value of speculatively changed L1 cache. Their speculative retirement schemes reduce pipeline stalls with better utilization of the instruction window, but it requires fair amount of additional hardwares to keep track of the speculative execution status and to enable precise roll-back. And their approach is based on sequential consistency(SC) and only have limited memory access overlapping.
The objective of this thesis is to design processor level architectural supports which increase the performance of DSMs using ILP mechanisms to hide large remote memory access delay. We designed independent private access(IPA) and memory access tagging(MAT) schemes for that purpose and developed a shared memory ILP multi processor simulator to evaluate our schemes and compare it with previous approaches.
IPA is based on two level memory access mechanisms of DSMs and it improves the performance by removing mutual consistent dependency with shared and private memory access. MAT have more sophisticated mechanisms, it is solely based on relaxed memory consistency model. Using newly defined ACQUIRE and RELEASE instructions while storing tags of memory access instructions in Access History Queue(AHQ), MAT scheme reduces rollback from mispredicted load instructions and also increase the level of memory access pipelining.
We evaluate the performance of the proposed IPA and MAT schemes via extensive simulation with various benchmark programs under a variety of processor configurations and lengths of remote memory access de-lay. We upgraded the famous MINT[1] simulator and named it sMINT to simulate ILP mechanisms on shared memory multiprocessor systems. Using sMINT, we can easily implement previously mentioned mechanisms and can perform fast simulation compared to other simulators.
Our simulation results show that IPA and MAT considerably improve the performance of DSMs and out performs other approaches on most benchmark programs.
현재의 마이크로프로세서들은 제한된 클럭사이클내에서 보다 많은 명령어들을 수행하기 위하여 복잡한 명령어 수준의 병렬성을 채용하고 있다. 이 병렬성은 명령어들을 미리 프로세서 내부에 올려놓고 순서에 관계없이 수행할 수 있는 것들을 미리 수행해 놓는 방식으로 순서바꿈 수행, 레지스터 재명명, 무정지 캐시, 분기 예측 등이 그 예이다. 단일 프로세서 시스템에서 많은 성능 향상을 끌어내는 이러한 기법들을 공유메모리 다중 프로세서 환경에서 그대로 수행할 경우 메모리 일관성 문제를 일으키게 된다. 공유 메모리 다중 프로세서 환경에서는 공유 메모리의 내용의 변경 순서가 모든 프로세서들에게 일관성 있게 보여져야 하나, 순서바꿈 수행을 통해 공유 메모리를 접근할 경우 실제 메모리의 변경 순서가 프로세서에게 다르게 보여지게 되어 의도되지 않은 수행결과가 발생할 수 있으며 이를 해결하기 위해 다양한 메모리 일관성 모델들이 제시되어 있다. 대칭적 다중프로세싱을 지원하는 기존의 프로세서들도 이러한 메모리 일관성 모델들을 지원하기 위한 여러가지 기능들을 가지고 있다. 대표적인 기능으로 메모리 배리어명령어들이 있으며 이러한 명령어들을 메모리 접근명령어 전후에 삽입함으로서 원하는 메모리접근 순서를 유지 시킬수 있다. 분산 공유 메모리시스템의 경우 버스 방식으로 연결되는 대칭적 다중프로세싱과는 달리 상호연결망을 통해 연결되는 대규모 멀티시스템의 형태를 가지고 있으며, 이로 인해 상대적으로 긴 공유메모리 접근 시간을 가지게 된다. 이러한 접근 시간의 지연은 분산 공유 메모리시스템의 성능에 가장 큰 영향을 미치며 이를 어떻게 극복하는가가 분산 공유 메모리시스템 설계의 가장 중요한 요소로 꼽히고 있다. 접근 지연을 극복하기 위해 접근시간동안에 다른 명령어들을 수행한다거나 긴 접근 시간을 가지는 명령어들을 중첩수행하는 방식이 사용된다. 다른 명령어들을 동시에 수행하는 방법은 명령어 수준의 병렬성을 이용하는 방법이고, 이때의 병렬성을 높이기 위해 메모리 접근을 예측하여 미리 수행할 수 있도록 해주는 기법들이 제안되어 있다. 또한 긴 접근시간을 가지는 명령어들의 중첩수행의 경우 완화된 형태의 메모리 일관성 모델을 통해 중첩수행의 허용도를 높이는 방법을 바탕으로 명령어 수준의 병렬성을 적용하고 있다. 본 논문에서는 분산공유메모리시스템의 긴 공유메모리 접근시간으로 인한 성능저하를 프로세서 수준에서 줄일 수 있는 기법들을 제안하고, 이를 실제 수행해 볼수 있게하는 시뮬레이터를 제작하여 검증하였다. 첫번째로, 독립된 비공유 메모리영역에 대한 접근을 일관성 유지 제한에서 독립시킴으로서 비공유 메모리 영역접근에 의한 명령어 수준의 병렬성제한을 제거시키는 기법인 비공유독립접근법을 제안하였다. 두번째로, 메모리 접근 추적법을 제안하였다. 이는 접근역사큐라는 프로세서가 읽어들인 명령어들 가운데 메모리 접근에 관련된 인스트럭션에 대한 정보를 모아놓은 큐형태의 아키텍쳐를 사용하여 일관성 유지를 깨뜨리지 않는 가능한 메모리 접근 명령들의 중첩수행들을 찾아 내는방법이다. 접근역사큐는 현재 프로세서의 일관성 유지 상태에 대한 상세한 정보를 제공함으로서 예측 수행된 메모리 접근 명령들의 폐기율을 줄이는 역할을 한다. 세번째로 sMINT라는 슈퍼스칼라 프로세서를 채용한 범용 공유메모리 다중 프로세서시스템 시뮬레이터를 개발하였고, 기존의 연구들과 본논문에서 제안된 기법들을 그 시뮬레이터에 구현하여 다양한 환경변수 하에서 성능비교를 할 수 있도록 하였다. 본 논문에서 제안한 기법들은 기존의 연구들에 비해 적은 하드웨어 코스트를 가지며, 시뮬레이션을 통해 비공유독립접근법의 경우 기존의 연구들에 적용하였을 때 그 연구들의 성능을 더욱 향상시킬 수 있음을, 메모리 접근 추적법의 경우 기존 연구들 보다 더 나은성능 향상을 보임을 확인하였다.