병렬 프로그램에서 성김도와 스케쥴링 정책들의 효과

정인범(In-Bum Jung),이준원(Joon-Won Lee) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.11

병렬 프로그램의 성능은 메모리 접근 지연시간과 동기화 지연시간에 의하여 제약을 받는다. 본 논문에서는 이들 지연 시간들의 효과를 조사하기 위하여 성김도 및 스케쥴링 정책들을 변경시키면서 병렬 프로그램들을 수행하였다. 성김도와 처리기 스케쥴링 정책들에 의하여 생성되는 메모리 참조 형태의 변화들은 병렬 프로그램의 캐쉬 성능과 동기화 기능에 영향을 미치고 있다. 본 논문에서는 수행 구동 모의 시험기를 통하여 성김도와 처리기 스케쥴링 정책들 사이의 상호 작용을 시험하였다. 모의 시험 결과는 프로그래머에 의해 선택된 그레인 크기와 스케쥴링 정책이 병렬 프로그램들의 캐쉬 동작 및 동기화 지연 시간에 현저한 영향을 미치고 있음을 보여준다. 이러한 상세한 모의 시험들을 바탕으로 모의 시험에서 사용된 병렬 프로그램들 각각에 대한 최적의 그레인 크기와 스케쥴링 정책을 제시하고 경과들에 대한 원인들을 분석하였다. The performance of parallel programs has suffered from the latencies caused by memory access and synchronization. To explore the effect of these latencies, we execute parallel applications varying the scheduling policies and grain sizes. The variations of the memory access patterns generated by the granularity and scheduling policies may affect the cache behavior and synchronization operation of the parallel applications. In this paper, the interactions between grain sizes and scheduling policies are examined through execution-driven simulations. The simulation results show that the grain size and scheduling policy selected by the programmers have significant impacts on the cache behavior and synchronization latency in most parallel programs. On the basis of the simulation studies, we suggest the best grain size and scheduling policy for each simulated parallel program, and analyze the causes inducing those results.

공유메모리 다중 프로세서에서 서브블록 캐쉬 프로토콜의 성능

정인범(In-Bum Jung),이준원(Joon-Won Lee) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.6

본 논문에서는 공유 메모리 다중 프로세서에서 서브 블록 캐쉬 일관성 프로토콜의 성능을 측정하였다. 쓰기 무효와 정책을 사용하는 캐쉬 프로토콜에서 캐쉬 블록의 크기가 클수록 캐쉬 메모리의 지역 공간성은 개선된다. 그러나 캐쉬 블록의 크기가 클수록 거짓공유에 의한 불필요한 캐쉬 블록 무효화가 발생되며 캐쉬 블록의 대체가 발생되었을 때 갱신된 부분뿐만 아니라 캐쉬 블록 전체를 전송하므로 버스의 교통량이 증가된다. 서브 블록 캐쉬는 데이터 일관성 유지 단위와 전송 단위를 구분하므로 이러한 문제점을 해결하는 방법이다. 본 논문에서는 캐쉬 쓰기 실패가 발생되었을 때 쓰기 할당 정책을 사용하므로 캐쉬 선인출 효과를 얻고 또한 기존의 서브 블록 캐쉬 프로토콜보다 적은 캐쉬 블록 상태를 갖는 개선된 서브 블록 캐쉬 프로토콜을 시험한다. 모의 시험을 통하여 제안된 서브 블록 캐쉬 프로토콜은 버스 교통량을 감소시키고 병렬 프로그램들의 성능을 향상시킴을 보인다. In this paper, we measured the performance of the subblock cache coherence protocol in the shared memory multiprocessor. When using the write invalidate cache protocol, the larger the cache block used, the locality of the cache memory is improved. However, the larger cache blocks increase the bus traffic caused by the unnecessary invalidation of the shared cache blocks incurred by the false sharing and its policy of transferring total cache block instead of partial updated parts on the cache block replacement. The subblock cache protocol addresses these problems based on the distinction between the coherence unit and transfer unit. In this paper, we examine an enhanced subblock cache protocol having data prefetching effects due to the write allocation scheme on cache write misses and also having fewer cache line states than existing subblock cache protocols. Simulation results show that the suggested subblock protocol improves the performance of the simulated parallel programs due to decreased bus traffic.

배리어 대기시간의 분석과 높은 프로세서 효율을 위한 동기화 프리미티브

정인범(In-Bum Jung),이준원(Joon-Won Lee) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.2

배리어 프리미티브는 병렬 프로그램을 수행할 때 계산에 참여한 프로세서들 사이에 동기화를 위하여 사용된다. 그러나 배리어에 일찍 도착한 프로세서들은 나머지 프로세서들이 배리어에 도착할 때 까지 배리어에서 기다리게 되므로 프로세서들의 활용율이 떨어진다. 본 논문에서는 배리어 대기시간의 원인들을 찾기 위하여 병렬 프로그램들을 다양한 그레인 크기들로 수행하였다. 모든 프로세서들이 동일한 갯수의 그레인들을 수행함에도 불구하고 그레인 크기에 따라 변화되는 명령어들과 캐쉬 실패들은 배리어 대기 시간에 영향을 미치고 있음을 시험한다. 또한 배리어에서의 맹목적 대기시간을 감소시키기 위하여 동기화 기능을 두 단계로 나누어 수행하는 두 단계 배리어를 제안한다. 모의실험 결과는 병렬 프로그램의 그레인 크기는 배리어 대기시간에 영향을 미치고 있음을 보여주며, 또한 제안된 두단계 배리어가 기존의 배리어 프리미티브 보다 배리어에서의 대기시간을 줄여주고 있음을 보여준다. Barrier is widely used method for synchronization in parallel applications. However, since the processors waiting for other processors to reach the barrier are idling, the processor utilization is decreased. In this paper, to find the sources of the barrier waiting time, parallel applications are executed on the various grain sizes. Even if all processors execute the identical number of grams, the barrier waiting times are affected by varying the number of instructions and cache misses attributed to the grain size. To reduce the waiting time at barriers, the 2-phased barrier concept is presented, that divides a synchronization operation of the processors into the two stages. The simulation results show that the grain size of the parallel programs has impact on the barrier waiting time and that the 2-phased barrier substantially reduces the barrier waiting time when compared against the existing barrier primitives.

스트라이드 배열 병합 방법의 데이타 선인출 효과

정인범(In-Bum Jung),이준원(Joon-Won Lee) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.11

데이타들에 대한 선인출 효과를 얻기 위하여 캐쉬 메모리의 캐쉬 블록은 다중 워드로 구성된다. 그러나 선인출된 데이타들이 사용되지 않을 경우 캐쉬 메모리가 낭비되고 따라서 캐쉬 실패율이 증가한다. 데이타 배열 병합 방법은 캐쉬 실패 원인의 하나인 캐쉬 충돌 실패를 감소시키기 위하여 사용되고 있다. 그러나 기존의 배열 병합 방법은 유용하지 못한 데이타들을 캐쉬 블록에 선인출하는 현상을 보인다. 본 논문에서는 이러한 현상을 개선한 스트라이드 배열 병합을 제안한다. 모의시험에서 캐쉬 블록이 다중 워드로 구성된 경우 스트라이드 배열 병합은 캐쉬 충돌 실패를 감소시킬 뿐 만 아니라 유용한 데이타 선인출을 증가 시키므로 캐쉬 성능을 향상시킴을 보여준다. 또한 이렇게 향상된 캐쉬 성능은 프로세서 증가에 따른 확장성 있는 프로그램 성능을 나타낸다. The cache memory is composed of cache lines with multiple words to achieve the effect of data prefetching. However, if the prefetched data are not used, the spaces of the cache memory are wasted and thus the cache miss rate increases. The data merging-arrays method is used for the sake of the reduction of the cache conflict misses. However, the existing merging-arrays method results in the useless data prefetching. In this paper, a stride merging-arrays method is suggested for improving this phenomenon. Simulation results show that when a cache line is composed of multiple words, the stride merging-arrays method increases the cache performance due to not only the reduction of cache conflict misses but also the useful data prefetching. This enhanced cache performance also represents the more scalable performance of parallel applications according to increasing the number of processors.

센서네트워크에서의 노드간 무선통신 성능 분석

정인범(In-Bum Jung),선주호(Ju-ho Seon),박총명(Chong-Myung Park),이좌형(Joa-Hyoung Lee),김윤(Yoon Kim) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2D

센서네트워크는 사람을 대신해 다양한 환경에서 감시와 정보수집 역할을 수행한다. 센서네트워크는 제한된 하드웨어 자원과 낮은 무선 네트워크 대역폭을 사용한다. 이러한 특성은 통신 중 높은 에러율을 발생시키며 데이터 신뢰도 향상을 위한 오류정정 기법의 필요성이 높다.센서노드의 환경에 따른CRC 에러와 패턴에 대한 연구는 오류정정 기법의 적절한 기법 선택을 위한 자료가 된다. 본 논문에서는 시스템 구성시 데이터 전송률에 영향을 미치는 전송주기와 센서노드간의 거리, 전송 패킷의 크기, RF의 크기에 대한 실험을 실시한다. 실험한 결과를 바탕으로 시스템 구성에서 고려해야 하는 요소를 알아본다.

데이터 병렬 프로그램에서 배리어 대기시간의 분석

정인범(Jung In Bum) 강원대학교 산업기술연구소 2001 産業技術硏究 Vol.21 No.1

Barrier is widely used for synchronization in parallel programs. Since the process arrived earlier than others should wait at the barrier, the total processor utilization decreases. In this paper, to find the sources of the barrier waiting time, parallel programs alee executed on the various grain sizes through execution-driven simulations. In simulation studies, we found that even if approximately equal amounts of work are distributed to each processor, all processes may not arrive at a barrier at the same time. The reasons are that the different numbers of cache misses and instructions within partitioned grains result in the difference in arrival time of processors at the barrier.

공유 버스상에서 프로그램 특성을 사용한 프로세서 할당 정책

정인범(In-Bum Jung),이준원(Joon-Won Lee) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.9

본 논문에서는 시스템 내의 프로세서들을 효과적으로 사용하기 위한 적응적 프로세서 할당정책을 제안한다. 프로그램의 병렬성을 향상시키기 위하여 일반적으로 병렬 처리에 사용될 프로세서 개수를 증가시킨다. 그러나 증가된 프로세서들은 그레인 크기에 변화를 일으키며 이는 캐쉬 성능에 영향을 미친다. 특히 대역이 제한된 공유 버스를 사용하는 시스템에서는 프로세서 개수의 증가는 공유 버스에 대한 접근 경쟁을 크게 증가하므로 버스에서 대기하는 시간이 프로세서 증가에 의한 계산 능력 이득을 상쇄시키는 주요한 원인이 되고 있다. 본 논문에서 제안한 적응적 프로세서 할당 정책은 프로그램이 수행되는 도중에 임의의 기간동안 공유버스에 대기중인 프로세서 분포에 관한 정보를 얻는다. 그리고 이 정보를 바탕으로 프로세서 개수를 변경하는 방법이다. 모의 시험에서 적응적 프로세서 할당 정책은 프로그램들의 버스 트래픽 특성에 따른 최적의 적합한 프로세서 개수를 발견함을 보인다. 그리고 적응적 프로세서 할당정책은 고정된 프로세서 개수를 사용한 가장 좋은 성능보다는 다소 떨어진 성능을 나타내었으나 시스템의 프로세서 활용성을 높여 효과적 시스템 사용에 기여함을 보인다. In this paper, the adaptive processor allocation policy is suggested to make effective use of processors in system To enhance the parallelism, the number of processors used in the parallel computing may be Increased. However, increasing thc number of processors affects the grain size of the parallel program. Therefore, it affects the cache performance In particular, when the shared bus is employed, since increasing the number of processors can result in a significant amount of contention to achieve the shared-bus, the Increased computing power is offset by the bus waiting time due to these contentions. The adaptive processor allocation policy acquires the information about the distribution of waiting processors on shared bus for any execution period of programs And it changes the number of processors working in parallel processing during thc program's run. Our simulation results show that the adaptive processor allocation policy finds the optimum feasible number of processors based on the bus traffic characteristic of programs Thus, it contributes to effective system utilization, even though it performs slightly less efficiently than using a fixed number of processors with the best performance.

거짓 공유를 제거하기 위한 캐쉬 프로토콜

정인범(In-Bum Jung),이준원(Joon-Won Lee),박승규(Seung-Kyu Park) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.6

버스기반 공유 메모리 다중 프로세서 시스템에서 시스템의 성능과 확장성은 캐쉬 일관성 유지를 위해 발생되는 버스 트래픽에 의하여 제약을 받는다. 다중 프로세서들이 동일한 캐쉬 블록내의 서로 다른 워드들을 참조하는 경우 데이터에 대한 공유가 실제 이상으로 과장될 수 있으므로 이런 과부하의 일부는 피할수 있다. 즉 데이터가 아닌 캐쉬 블록 자체만이 공유된 경우에도 데이터가 공유된 것처럼 취급하므로 발생되는 이런 현상을 거짓 공유 현상이라고 한다. 본 논문에서는 거짓 공유를 제거하기 위한 워드 단위 캐쉬 프로토콜이라 지칭된 프로토콜을 제시 하였다. 또한 새로이 제시된 캐쉬 프로토콜의 성능측정을 위하여 수행 구동 모의 시험 모델을 사용하였다. 우리는 모의 시험기 상에서 여러 병렬 응용 프로그램들을 구동하여 발생되는 거짓 공유 및 버스 트래픽의 양을 측정하였다. 이러한 모의 시험을 통하여 동일한 작업 부하내 에서는 새로 제안된 프로토콜이 기존 무효화 프로토콜보다 더욱 적은 버스 트래픽을 발생하고 있음을 알게 되었다. The performance and scalibility of bus based shared memory multiprocessors is limited by the amount of the bus traffic most of which generated by cache coherence overhead. Some of this overhead is avoidable, since data sharing is exaggerated when multiple processors access different words in same cache line This phenomenon is called false sharing since hardware treats it as if data is shared even though the cache line containing the data is actually not shared. In this paper we present a new cache coherence protocol called word unit cache protocol to eliminate the false sharing in the cache coherence protocol. We use a simulation model to study the performance of a new protocol and to compare with the existing write invalidation cache protocol We measure the amount of the false sharing and the bus traffic in several coarse-grained parallel applications. The result of the Simulation indicates that the new cache protocol causes less bus traffic than the other write invalidation protocols.

직접 사상 캐쉬의 캐쉬 실패율을 감소시키기 위한 성김도 정책

정인범(In-Bum Jung),공기석(Ki-sok Kong),이준원(Joon-Won Lee) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.7

높은 캐쉬 구역성을 나타내는 데이터 병렬 프로그램들에서 그레인 크기의 선정은 캐쉬 성능에 커다란 영향을 미친다. 선택된 그레인 크기가 프로세서들 사이에 균등한 부하 배분을 제공하더라도 내재하는 캐쉬 효과를 무시한 그레인 크기는 하나의 프로세서에 할당된 그레인들 사이에 주소 간섭을 발생되게 한다. 이런 주소 간섭은 캐쉬 충돌 실패를 발생하기 때문에 캐쉬 구역성에 부정적 영향을 미치게 된다. 이러한 문제점을 해결하기 위해서 본 논문에서는 직접 사상 캐쉬의 특징을 바탕으로 캐쉬 크기와 프로세서 개수들로부터 최적 그레인 크기를 유도한다. 제안된 방법은 캐쉬 공간 내에서 그레인들이 동일한 주소로 사상 되지 않게 하므로 캐쉬 충돌 실패를 감소시킨다. 모의 시험 결과는 제안된 최적 그레인 크기는 직접사상 캐쉬상에서 캐쉬 실패를 줄이므로 시험된 데이터 병렬 프로그램들의 성능을 개선시킴을 보인다. In data parallel programs incurring high cache locality, the choice of grain sizes affects cache performance. Though the grain sizes chosen provide fair load balance among processors, the grain sizes that ignore underlying caching effect result in address interferences between grains allocated to a processor. These address interferences appear to have a negative impact on the cache locality, since they result in cache conflict misses. To address this problem, we propose a best grain size driven from a cache size and the number of processors based on direct mapped cache's characteristic. Since the proposed method does not map the grains to the same location in the cache, cache conflict misses are reduced. Simulation results show that the proposed best grain size substantially improves the performance of tested data parallel programs through the reduction of cache misses on direct-mapped caches.

데이타 배열을 사용하는 병렬 프로그램에서 그레인 크기를 이용한 데이타 선인출 기법

정인범(In-Bum Jung),이준원(Joon-Won Lee) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.1

데이타 선인출 방법은 데이타 참조와 프로세서 계산의 중첩을 이용하여 주메모리 접근 지연시간을 줄여주는 효과적인 방법이다. 그러나 선인출된 데이타가 캐쉬 메모리에 있는 다른 유용한 데이타들을 대체시키거나 또한 선인출된 데이타가 사용되지 않는 무익한 선인출일 경우 프로그램의 성능은 저하된다. 이러한 현상은 향후 사용되는 데이타들에 대한 정확한 예측이 부족하므로 발생된다. 병렬 프로그램이 계산을 위하여 데이타 배열들을 사용할 때 그레인 크기는 향후 사용되는 데이타 지역의 범위를 나타내므로 데이타 선인출을 위한 유용한 정보이다. 이런 정보를 기반으로 본 논문에서는 병렬 프로그램의 그레인 크기를 이용한 새로운 데이타 선인출 방법을 제안한다. 모의시험에서 제안된 선인출 방법은 기존의 선인출 방법들보다 버스 트랜잭션을 감소시킬 뿐만 아니라 유용한 선인출의 증가로 시험된 병렬 프로그램들의 성능을 향상시킨다. The data prefetching scheme is an effective technique to reduce the main memory access latency by exploiting the overlap of processor computations with data accesses. However, if the prefetched data replicate the useful existing data in the cache memory and they are not being used in computations. performances of programs are aggravated. This phenomenon results from the lack of correct predictions for data being used in the future. When parallel programs exploit the data arrays for computations, the grain size is useful information for data prefetching scheme because it implies the range of data using in computations. Based on this information, we suggest a new data prefetching scheme exploited by the grain size of the parallel program. Simulation results show that the suggested prefetching scheme improves the performance of the simulated parallel programs due to the reduction of bus transactions as well as useful prefetching operations.