공유 레지스터를 이용한 효율적인 프로세서간 통신 및 동기화 기법

민상렬(Sang Lyul Min) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.4

공유 메모리의 접근 제어 시간은 다단계 상호 연결망을 가지는 공유 메모리 다중 프로세서의 성능에 지대한 영향을 끼친다. 이러한 접근 제어 시간을 감소시키기 위하여 캐쉬(cache) 또는 선인출 (prefetch)기법을 사용할 수 있으나, 캐쉬의 경우에는 캐쉬 일관성 유지 문제 때문에, 선인출 기법인 경우에는 동기화에 의한 제약 때문에 그다지 큰 성능 향상을 기대하기 어렵다. 본 논문에서는 이러한 공유 메모리의 접근 제어 시간, 그중에서도 특히 공유 변수의 접근 제어 시간을 줄이기 위하여, 인접한 프로세서 사이에 위치하는 type 1 super register와 상호 연결망 내의 노드(node)에 위치하는 type 2 super register를 제안하였다. 본 논문에서는 이러한 super register를 공유 메모리 대신으로 사용하고 동기화 기법으로 full/empty비트 기법을 사용하는 경우 (1) Do 루프의 효율적인 무순서 (out of order) 수행 (2) 효율적인 동기화와 데이타 이동 (3) 공유 변수의 효율적인 분산에 매우 효과적임을 보였다.또한 본 논문에서는 이러한 super register를 이용한 실제 프로그래밍 예를 통하여 성능 향상을 예를 보였다. The speed of access to shared global memory is a critical aspect in the performance of shared memory multiprocessors interconnected by a multistage interconnection network. Neither shared data caching, because of the difficulty of enforcing cache coherence in this type of architecture, nor shared data prefetching, because of the synchronization problems, appears to be a viable option from the performance viewpoint. In order to reduce the effective fetch time of operands which specify shared read/write variables, we propose the concept of “super registers”. Super registers of type 1 are registers shared by adjacent processors in a bidirectional linear structure. Super registers of type 2 are embedded in the switches of the interconnection network. We show that the combination of access to these registers (rather than to global memory) and synchronizations based on full/empty bits in these registers can be effective for several parallel programming paradigms such as (1) efficient out of order execution of Do loop body (2) efficient synchronizations and data movements (3) distribution of variables, especially of shared arrays. We conclude this paper by showing how super registers would speed up the computation of some example programs.

RISC 프로세서를 위한 시간분석 도구의 자동 생성

민상렬(Sang Lyul Min),신현식(Heonshik Shin),이병도(Byung-Do Rhee) 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.11

실시간 시스템에 사용되는 RISC 프로세서에서 프로그램의 최악 실행시간을 정확하게 계산하기 위하여는 명령어 파이프라인과 캐쉬메모리의 시간적 영향을 고려하여야 한다. 이들의 시간적 형태의 분석을 위하여 확장 타이밍스키마 기법과 이에 기초한 기계 종속적인 시간분석 도구가 이용되고 있다. 이 논문에서는 시간분석 도구의 기계 종속성 문제를 해결하여 이식성을 높이기 위한 방법으로 시간분석 도구 생성기를 제안한다. 시간분석 도구 생성기는 입력으로 주어지는 마이크로 프로세서의 아키텍쳐 사양으로부터 추출한 기계 종속적인 정보를 사용하여 목표 프로세서의 시간분석 도구를 자동 생성한다. 시간분석 도구 생성기는 다양한 마이크로프로세서의 연구개발과 계속적인 아키텍쳐의 진화에 유연하게 대처할 수 있는 수단을 제공한다. Real-time systems with RISC processors require that timing effects of pipelined execution and cache memory should be accurately analyzed to predict the worst case execution time of a program. For the analysis of their timing behavior, a timing analysis method, called extended timing schema, and a machine-dependent timing tool based on this schema have been developed. We propose a retargetable timing analyzer generator (RTAG) to resolve the machine-dependency problem of the timing tool and improve its portability The RTAG automatically generates a pipeline analyzer using machine-specific information extracted from an architecture description of microprocessor which is given as input data. It provides a powerful tool that, with high flexibility, enables us to cope with the rapid progress in microprocessor technologies which continue to evolve and diversify.

다중프로세서 UNIX 커널의 병목현상 분석

민상렬(Sang Lyul Min),김길용(Gil Yong Kim) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.10

본 논문은 공유 메모리 다중프로세서 구조를 가진 컴퓨터 시스템의 다중프로세서 UNIX 커널에 대한 성능 측정 내용을 기술하고 있다. 성능 측정에는 다양한 종류의 마이크로(micro)및 마크로(macro) 벤치마크 프로그램들이 프로세서의 갯수별로 수행되었으며, 각각에 대한 경과 시간과 함께 커널의 lock 경쟁에 대한 자료가 수집되었다. 이 자료의 분석을 통하여 커널의 run queue와 buffer free list의 spin lock에 대한 경쟁률이 매우 높음을 발견하였으며 (6개의 CPU에 대하여 각각 52%와 37%), 따라서 운영체제의 프로세스 스케쥴링 기능과 버퍼 관리 기능에 병목현상이 발생하고 있음을 알 수 있었다. 또한, 본 연구에서는 인터럽트 처리 루틴들이 경쟁률이 높은 이 두 lock들에 대하여 spinning함으로써 크게 지연되고 있음을 발견하였다. 한편, 여섯개의 프로세서들로 이루어진 다중 프로세서상에서의 벤치마크 수행에 대한 커널 프로화일링의 결과는 전체 수행 시간(CPU time)의 약 22%가 이 두 spin lock의 획득을 위해 소요되고 있음을 보여줌으로써, 두 lock에 대한 경쟁으로 인한 시스템 성능의 저하가 얼마나 심각한지를 보여주고 있다. 결론적으로, 본 연구는 위의 두 lock에 대한 경쟁의 해소가 시스템의 성능과 확장성을 크게 향상시킬 수 있음을 보였다. This paper presents the performance measurements of a UNIX kernel for a shared-memory multiprocessor. As a methodology, we adopt micro and macro benchmarking for the varying numbers of processors and present the results in terms of the total execution times and lock contention rates. The analysis of performance measurements shows that the contention rates for the run queue lock and the buffer free list lock are very high (52% and 37% for 6 CPUs, respectively). This indicates that the process scheduling routine and the buffer free list management routine are the major bottlenecks of the multiprocessor operating system we analyzed. The results also show that the interrupt processing is severely delayed due to the spinning on the aforementioned locks. As a result, the performance of the multiprocessor system is severely crippled by the contention for the above locks (about 22% of the total CPU time is spent for the spinning on the above two locks). This paper concludes that the elimination of contention on the two locks will greatly improve the performance and scalability of the system.

최적화된 프로그램의 최악 실행시간 분석

임성수(Sung-Soo Lim),김지홍(Jihong Kim),민상렬(Sang Lyul Min) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.1A

본 논문에서는 최적화된 프로그램에 대해 계층적인 최악 실행시간 분석 기법을 적용할 때의 문제점을 파악하고, 이를 해결하기 위한 방법을 제시한다. 제시하는 방법은 컴파일러가 최악 실행시간 분석에 도움을 줄 수 있는 정보를 컴파일 단계에서 추출하여 생성하고, 이 정보를 시간 분석기가 이용하여 최적화된 프로그램의 최악 실행시간을 분석하는 것이다. 제안하는 기법은 컴파일러의 전반적 수정을 요구하기 때문에, 본 논문에서는 컴파일러의 수정 없이 제안하는 기법을 우회적으로 구현한 시간 분석기를 사용하여 기법의 적용 가능성을 알아 본다. 시간 분석기는 VLIW 프로세서를 기반으로 하여 구현되었으며, 해당 프로세서의 시뮬레이터로부터 얻은 실제 실행시간과 비교했을 때 정확한 분석 결과를 보였다.

FAT 호환 플래시 메모리 파일 시스템을 위한 성능 최적화 기법

김성관(Sung-Kwan Kim),이동희(Dong-Hee Lee),민상렬(Sang Lyul Min) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

최근 휴대용 단말기 및 임베디드 시스템 등을 위한 저장 장치로서 플래시 메모리가 각광받고 있다. 이 때 저장 장치 관리를 위한 플래시 메모리 파일 시스템의 역할이 중요한데, 이를 위해 전용 플래시 메모리 파일 시스템이 제안되기도 했지만 산업계에서는 사실상의 표준으로 FAT 파일 시스템이 광범위하게 사용되고 있다. 그러나 FAT 파일 시스템은 플래시 메모리의 물리적 특성을 고려하지 않고 설계되었기에 성능상 개선의 여지가 있다. 본 논문에서는 FAT 파일 시스템을 대상으로 플래시 메모리의 동작 특성을 고려한 성능 최적화 기법을 제안한다. 구체적으로 본 논문에서 제안되는 기법은 파일 삭제 시 FAT 파일 시스템의 기본 동작을 확장한 것으로 플래시 메모리 위에서 동작하는 FAT 파일 시스템의 쓰기 성능을 개선하는 효과를 보여 준다. 실험 결과 약 29%의 쓰기 성능 개선 효과가 있음을 확인할 수 있었다.

다중 이슈 프로세서를 위한 최악 실행시간 분석 기법

임성수(Sung-Soo Lim),한정희(Jung Hee Han),김지홍(Jihong Kim),민상렬(Sang Lyul Min) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.10

논문에서는 한 번에 여러 개의 명령어를 이슈할 수 있는 다중 이슈 프로세서(in-order, multiple-issue processors)에 대해 최악 실행시간을 분석하는 기법을 제시한다. 명령어들의 이슈 행태를 분석하기 위해서 명령어들 사이의 의존성 관계를 표현하는 IDG(Instruction Dependence Graph)라고 하는 자료구조를 사용한다. 이 자료구조로부터 각 명령어들의 이슈간 거리 범위를 구하고, 프로그램의 계층적인 분석 과정에서 점차로 더 정확한 이슈간 거리 범위로 갱신한다. 프로그램의 최악 실행시간은 최종적으로 얻어진 프로그램 전체에 대한 IDG를 분석하여 얻은 명령어들의 이슈간 거리 범위로부터 계산한다. 제안하는 기법을 구현한 시간 분석기를 사용하여 실험한 결과, 논문에서 사용한 다중 이슈 프로세서 모델에 대해서 정확하게 다중 이슈 행태를 분석할 수 있었다. In this paper, we present a worst case timing analysis technique for in-order, multiple-issue processors. In the proposed technique, timing information for each program construct is represented by a directed acyclic graph (DAG) that encodes dependences among nodes (i.e., instructions). From this information, we calculate for each pair of instructions distance bounds between their issue times. The worst case execution time of a program is calculated by progressively refining the distance bounds through hierarchical analysis over the program's syntax tree. Our experimental results show that the proposed technique can predict the worst case execution times for in-order, multiple-issue processors as accurately as for simpler RISC processors.

파이프라인 실행 구조의 최악 실행시간 분석기법

임성수(Sung-Soo Lim),배영현(Young Hyun Bae),민상렬(Sang Lyul Min),박창윤(Chang Yun Park),박근수(Kunsoo Park),신현식(Heonshik Shin),김종상(Chong Sang Kim) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.6

실시간 시스템을 구성하고자 할 때 중요한 요소 중의 하나는 시스템을 구성하는 작업들의 최악 실행시간(Worst Case Execution Time : WCET)을 예측하는 것이다. 이에 따라 지금까지 최악 실행시간 분석에 관한 많은 연구가 진행되어 왔다. 그러나 이들 연구에서는 최근에 많이 사용되는 RISC 프로세서 내부의 캐쉬 구조와 파이프라인 실행 구조에 대한 고려를 하지 않았다. 따라서 많은 경우 분석 결과는 실제 실행시간과 많은 차이를 보였다. 본 논문에서는 파이프라인 실행 구조에 의한 영향을 반영하여 최악 실행시간을 분석하기 위해 기존의 타이밍 스키마(Timing Schema)를 확장한 확장된 타이밍 스키마(Extended Timing Schema)를 제안한다. 확장된 타이밍 스키마에서는 실행시간 정보로서 기존 타이밍 스키마의 단순한 실행시간 범위(time-bound) 대신 파이프라인된 중첩 실행으로 인한 영향을 반영한 최악 실행시간 정보(Worst Case Timing Abstraction : WCTA)를 실행블럭 별로 유지한다. 그리고, 이들에 대해서 접속(concatenation)과 절지(pruning)라고 하는 새로운 연산을 계층적으로 적용해 가며 최악 실행경로에 포함될 가능성이 있는 경로들의 최악 실행시간을 분석한다. 본 논문에서는 제안하는 분석 기법에 따라 구현된 실행시간 분석기를 사용하여 프로그램의 최악 실행시간을 분석한 실험 결과를 제시한다. 실험에서 확장된 타이밍 스키마를 이용해 실행블럭들 사이의 파이프라인 실행에 의한 중첩실행 가능성을 최대한 반영할 때, 이를 고려하지 않을 때보다 약 50%까지 더 실제 실행 시간에 가까운 결과를 얻을 수 있었으며, 이 결과는 실제 측정된 실행시간에 매우 근접하는 것이었다. The estimation of a task′s WCET (Worst Case Execution Time) is crucial for real-time systems. But in many of the previous works, the timing effects of modern RISC processors′ pipelined execution and cache memory are not taken into account. Such a pessimistic approach would yield an extremely loose WCET bound. This paper propose the Extended Timing Schema which is revised from the original Timing Schema to reflect the timing effects of pipelined execution. In the Extended Timing Schema. the WCTA (Worst Case Timing Abstraction), which is defined to reflect the timing variations due to pipelining, is kept for each execution block that might be a part of the WCEP (Worst Case Execution Path) instead of simple time-bound of the original timing schema. And the newly defined operations such as concatenation and pruning are applied to WCTAs hierarchically along the program syntax tree until the WCET of the program can be obtained. This paper also reports on results of WCET analysis. Our results show that up to 50% tighter WCET bounds can be obtained by considering overlapped execution between the program constructs due to pipelining, and the analyzed WCETs are very close to the measured execution times.

RISC 프로세서를 대상으로 한 최악 실행시간 분석의 정확도에 대한 과예측 원인별 영향 분석

김성관(Sung-Kwan Kim),민상렬(Sang Lyul Min),하란(Rhan Ha),김종상(Chong Sang Kim) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.4

실시간 태스크의 최악 실행시간을 예측할 때 과예측이 발생하는 원인은, 첫째 프로그램의 동적인 최악 실행 행태를 정적으로 분석하는 것이 근본적으로 어렵기 때문이며, 둘째 최근의 RISC 형태 프로세서에 포함되어 있는 파이프라인 실행 구조와 캐쉬 등이 그러한 정적 분석을 더욱 어렵게 만들기 때문이다. 그런데 기존의 연구에서는 각각의 과예측 원인을 해결하기 위한 방법에 대해서만 언급하고 있을 뿐 분석의 정확도에서 각 원인이 차지하는 비중에 대해서는 언급하고 있지 않다. 이에 본 연구에서는 최악 실행시간 예측시 과예측을 유발하는 원인들, 즉 분석 요소들의 영향을 정량적으로 조사함으로써 기존의 최악 실행시간 분석 기법들이 보완해야 할 방향을 제시하고자 한다. 본 연구에서는 실험이 특정 분석 기법에 의존하지 않도록 하기 위하여 시뮬레이션 방법에 기반한다. 이를 위해 분석 요소별 스위치가 포함된 MIPS R3000 프로세서를 위한 시뮬레이터를 구현하였는데, 각 스위치는 해당 분석 요소에 대한 분석의 정확도 수준을 결정한다. 모든 스위치 조합에 대해서 시뮬레이션을 반복 수행한 다음 분산 분석을 수행하여 어떤 분석 요소가 가장 큰 영향을 끼치는지 고찰한다. Existing analysis techniques for estimating the worst case execution time (WCET) of real-time tasks still suffer from significant overestimation due to two types of overestimation sources. First, it is unavoidably difficult to predict dynamic behavior of programs statically. Second, pipelined execution and caching found in recent RISC-style processors even more complicate such a prediction. Although these overestimation sources have been attacked in many existing analysis techniques, we cannot find in the literature any description about questions like which one is most important Thus, in this paper, we quantitatively analyze the Impacts of overestimation sources on the accuracy of the worst case timing analysis. Using the results, we can identify dominant overestimation sources that should be analyzed more accurately to get tighter WCET estimations. To make our method independent of any existing analysis techniques, we use simulation based methodology. We have implemented a MIPS R3000 simulator equipped with several switches, each of which determines the accuracy level of the timing analysis for the corresponding overestimation source. After repeating simulation for all of the switch combinations, we perform the variance analysis and study which factor has the largest impact on the accuracy of the predicted WCETs.

순차 참조와 순환 참조들을 고려한 버퍼 캐쉬 관리 기법

김종민(Jong Min Kim),최종무(Jongmoo Choi),김제성(Jesung Kim),이동희(Donghee Lee),노삼혁(Sam H. Noh),민상렬(Sang Lyul Min),조유근(Yookun Cho),김종상(Chong Sang Kim) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.1·2

최근 버퍼 캐쉬의 성능을 향상시키기 위한 많은 블록 교체 기법들이 제안되었으며 이 중에서 작업 집합 (working set) 변화에 잘 적응하고 구현이 용이한 Least Recently Used (LRU) 블록 교체 기법이 널리 사용되고 있다. 그러나 LRU 블록 교체 기법은 블록들이 규칙적인 참조 패턴을 보이면서 순차 참조되거나 순환 참조될 때 이 규칙성을 적절히 이용하지 못해 성능이 저하되는 문제점을 가진다. 본 논문에서는 다중 응용 트레이스를 이용하여 LRU 블록 교체 기법의 문제점을 관찰하고, 이 문제점을 해결하는 통합된 형태의 효율적인 버퍼 관리 (Unified Buffer Management, 이하 UBM) 기법을 제안한다. UBM 기법은 순차 참조 및 순환 참조를 자동 검출하여 분리된 공간에 저장하고 이들 참조에 적합한 블록교체 기법으로 이 공간을 관리한다. 또한 순차 참조와 순환 참조를 위한 공간과 나머지 참조를 위한 공간의 비율을 최적으로 할당하기 위해 온라인에서 수집된 정보를 이용하여 계산된 단위 공간 증가당 예상 버퍼 적중 증가율을 이용한다. 다중 응용 트레이스 기반 시뮬레이션 실험에서 UBM 기법의 버퍼 적중률은 LRU 블록 교체 기법에 비해 평균 12%, 최대 28%까지 향상된 결과를 보였다. The Least Recently Used (LRU) block replacement scheme is still widely used due to its simplicity. While simple, it still adapts well to the changes of the working set, and has been shown to be efficient when recently referenced blocks are likely to be re-referenced in the near future. The main drawback of the LRU scheme, however, is that it exhibits performance degradations because it does not make use of reference regularities such as sequential and looping references. In this paper, we present the Unified Buffer Management (UBM) scheme that exploits these regularities and yet, is simple to deploy. The UBM scheme automatically detects sequential and looping references and stores the detected blocks in separate partitions of the buffer cache. These partitions are managed by appropriate replacement schemes based on their detected patterns. The allocation problem among the divided partitions is also tackled with the use of the notion of marginal gains. The performance gains obtained through the use of this scheme are substantial. Trace-driven simulation experiments show that the hit ratios improve by as much as 28% (with an average of 12%) compared to the LRU scheme for the traces we considered.

문맥 교환으로 인한 캐쉬 접근 실패를 줄이는 precharging 캐쉬 구조

김종민(Jong Min Kim),이민석(Minsuk Lee),박명순(Myung Soon Park),민상렬(Sang Lyul Min),정덕균(Deog-Kyoon Jeong),신현식(Heonshik Shin),김종상(Chong Sang Kim) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.7

최근 캐쉬를 사용하는 고속의 프로세서들이 출현하면서 캐쉬 접근 실패를 처리하기 위해 소요되는 프로세서 싸이클 수가 전체 수행 시간에서 차지하는 비중은 계속해서 높아지고 있다. 특히 문맥 교환으로 인하여 발생하는 캐쉬 접근 실패는 캐쉬의 크기와 연관도가 증가할수록 전체 캐쉬 접근 실패의 많은 비중을 차지한다. 본 논문에서는 이러한 문맥 교환으로 인한 캐쉬 접근 실패를 줄일 수 있는 precharging 캐쉬 기법을 제안한다. 이 기법의 핵심은 프로세스가 문맥 교환되고 어느 정도의 시간이 지난 후에 발생되는 캐쉬와 메모리 사이의 유휴 메모리 대역폭을 이용하여 다음에 수행될 프로세스의 캐쉬 상태를 프로세스가 수행되기 이전에 미리 캐쉬에 읽어오는 것이다. 즉 캐쉬에서 해제된 각 블록들의 주소 정보와 프로세스 식별자를 이용하여 해당 프로세스가 수행되기 전에 미리 캐쉬에 필요한 블록을 적재하는 것이다. 이렇게 함으로써 해당 프로세스가 수행될 때에는 자신의 작업 집합(working set)이 이미 캐쉬 내에 존재하므로 다른 프로세스와의 캐쉬 블록 충돌에 의해 발생하는 접근 실패를 겪지 않는다. 본 논문에서 제시한 precharging 캐쉬 기법에 의한 성능 향상은 BACH 트레이스를 사용한 시뮬레이션으로 검증 하였으며, 그 결과 전체 발생하는 캐쉬 접근 실패의 0.68-9.52% 정도를 줄일 수 있고, 사용자 모드에서 발생하는 캐쉬 접근 실패의 2.81-15.3% 정도를 줄일 수 있음을 보였다. In current high-performance processors with cache memories, the relative cast of a cache miss in terms of processor cycles is becoming higher. As the size and set associativity of cache memory increase, the cache misses resulting from context switches take an increasingly large portion of total cache misses. In this paper, we propose and analyze a novel cache organization, called precharging cache, that aims at reducing the number of cache misses resulting from context switches. The key to the proposed scheme is to precharge the cache with the cache contents of next-to-be-scheduled process by making use of the idle bus bandwidth between the cache and main memory near the end of time quantum. In the proposed cache organization, the cache contents of the next-to-be-scheduled process are loaded into the cache before the execution using the block address and the process id information of the previously displaced cache blocks. This precharging strategy reduces the cache misses due to context switches since the working set is already in the cache by the time a process resumes execution. A quantitative performance evaluation based on trace-driven simulation using BACH traces reveals that the precharging cache scheme reduces the total cache misses by 0.68-9.52% and the user-mode cache misses by 2.81-15.3%.