다중 루프의 비 대칭 할당을 통한 병렬 처리

김석일(Sukil Kim) 한국정보과학회 1990 한국정보과학회 학술발표논문집 Vol.17 No.2

다중루프의 병렬처리 기법은 가용한 프로세서의 수를 몇개의 그룹으로 나누고 각각의 그룹이 다중 루프의 각 루프별로 병렬처리하는 방법이다. 기존의 대칭형 루프병렬화 기법은 다중루프의 중첩루프의 레벨에 따라 프로세서를 몇개의 그룹으로 나누고 각 그룹의 프로세서를 내측루프(inner loop)의 병렬처리에 이용하는 방안이다. 그러나 역방향 자료종속관계(backward data-dependence relation) 내에 루프 블럭이 존재하는 다중루프는 대칭형 루프병렬화 기법을 적용해도 최적의 결과를 얻을 수 없다. 본 논문에서는 이러한 루프의 경우에 사용될 수 있는 비대칭형 루프병렬화 기법을 제안하고 시뮬레이션을 통하여 그 효과를 입증하였다.

계층적 클러스터 하이퍼큐브 네트웍

김석일(Sukil Kim),이영성(Young-Sung Lee) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.2

계층적 클러스터 하이퍼큐브 다중처리기(Hierarchical Cluster Hypercube Multiprocessor HCHM)는 대단위 연산소자를 포함하는 네트웍에 적합한 계층구조를 가진 다중처리기이다. 제안된 HCHM은 기존의 하이퍼큐브 노드를 클러스터로 대치한 구조이다. 클러스터는 노드의 통신망을 지원하는 클러스터 제어용 프로세서에 여러개의 연산용 프로세서를 성형(星形)으로 연결한 다중처리기 시스템이다. 본 논문에서는 기존의 하이퍼큐브와 그 성능이 동일하나 시스템의 구성비용이 저렴한 최적설계 방안을 제시하였으며, 연구결과 클러스터를 구성하는 연산용 프로세서의 수를 두개로 하는 경우에는 기존의 하이퍼큐브와 동일한 성능을 가지나 시스템 구성비용이 2/3배로 적다. 또한 HCHM(m, 2)는 Qm-1 네트웍의 경로배정을 모의할 수 있으므로 메쉬, 링구조 및 이진트리 구성이 용이하다. 이외에도 제안된 HCHM구조를 구성하는 클러스터 제어용 프로세서와 연산용 프로세서별로 경로배정 및 통신 알고리즘도 제시하였다.

PALM 시스템의 병렬 라이브러리 설계 및 시스템의 통신과 연산 성능 평가

김석일(Sukil Kim),이영성(Young-Sung Lee) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.1

PALM시스템은 두개의 연산 프로세서를 버스로 연결하여 하나의 클러스터로 구성하고 각각의 클러스터를 하이퍼큐브 네트웍으로 연결하여 시스템내의 통신을 이중으로 하는 계층구조의 클러스터 컴퓨터로 충북대학교 병렬처리 및 프로그램언어 연구실에서 개발중이다. 본 연구에서는 PALM에 적합한 시스템 프로그램과 병렬처리를 지원하는 루틴을 설계하고 이를 PALM/286 test-bed에서 구현하였으며 시스템에서의 통신과 연산에 관한 성능평가를 수행하였다. 실험결과 PALM/286은 밀결합 다중 프로세서 시스템의 성능을 지니는-메세지 패싱에 의한 프로세서간 통신이 이루어지는-소결합 다중 프로세서 시스템임이 밝혀졌다. 아울러 본 논문에서 제안한 시스템 루틴과 병렬처리 라이브러리의 정확성도 확인되었다.

이층구조인 클러스터 하이퍼큐브 네트웍의 설계

김석일(Sukil Kim) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.12

본 논문에서는 TCHM(m, p)로 명명된 이층구조의 클러스터 하이퍼큐브를 설계하고 이를 분석하였다. 여기서 TCHM(m, p)는 통신프로세서마다 m개의 통신 포트를 가지고 있으며 연산프로세서와의 연결에 사용되는 포트의 수가 p개이며, 나머지 (m-p)개의 포트는 CP들을 (m-p) 차원 하이퍼큐브를 구성하는 데 사용된다. 표현할 수 있는 네트웍 위상이 star 네트웍인 TCHM(m, m)으로부터 기존의 하이퍼큐브인 TCHM(m, 1)에 이르기까지 다양한 TCHM(m, p) 중에서 TCHM(m, 2)는 시스템을 구성하는 AP의 수가 최대이나 시스템 구성비용이 최소인 비용 최적 시스템이다. 본 논문에서는 TCHM(m, 2)의 특징을 연구하였으며, 적용할 수 있는 통신 알고리즘도 제안하였다. 또한 TCHM(m, 2)의 평균경로길이가 (m-1)차원 하이퍼큐브의 평균경로길이에 비하여 짧음을 확인하였다. This paper designs and analyzes two-level clustered hypercube multiprocessor networks, which we call TCHM(m, p), where m denotes the number of ports of each communication processor (CP), and p is the number of ports interconnecting p application processors (APs) to a CP. Thus, m-p ports are used to connect CPs to construct an m-p dimensional hypercube. Among the wide spectrum of TCHM(m, p) network topologies, from a star, TCHM(m, m) to an ordinary hypercube, TCHM(m, 1), TCHM(m, 2) is an cost optimal topology among TCHM(m, p)s, such that TCHM(m, 2) minimizes the system cost while maximizing the number of APs in the system. 1n this paper, we explore properties of the network and propose a communication algorithm for the system. We also conclude that the average distance on TCHM(m, 2) is less than that on an (m-l) dimensional hypercube.

분산메모리형 다중프로세서 시스템에서 다행관측행렬의 병렬 Downdating기법

김석일(Sukil Kim),이충한(Chung-Han Lee) 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.12

This paper introduces a new parallel HUGD (Householder Updating and Givens Downdating) algorithm, that would shorten the overall computation-time complexity compared with that of the existing parallel GCFD algorithm. The parallel HUGD algorithm consists of two stages; the first stage is to produce a Cholesky factor of a multiple-row observation matrix by a parallel QR-factorization procedure; the second stage is to downdate the Cholesky factor through the parallel GCFD. Since the parallel GCFD of the second stage performs Columnwise parallel operations, the parallel QR-factorization of the first stage also performs columnwise parallel Householder reflections Such an alignment between two stages would eliminate a parallel transpose of the Cholesky factor, and thus, the overall computation time complexity of the parallel HUGD can be lesser than that of the parallel GCFD. As the proposed algorithm requires recursive message broadcasting, the algorithm can be applicable on distributed memory multiprocessor systems that equip broadcasting features. 본 논문에서는 기존의 병렬 GCFD(Givens Cholesky Factor Downdating)기법과 비교하여 시간복잡도가 개선된 병렬 HUGD(Householder Updating and Givens Downdating)기법을 제안하였다. 병렬 HUGD기법은 다행관측행렬을 병렬 QR-분할을 이용하여 상삼각행렬로 변환하고 계산된 상삼각행렬을 기존의 병렬 GCFD(Givens Cholesky Factor Downdating)로 downdating하는 두 가지 단계로 구성되어 있다. 특히, 제안된 기법의 두 번째 단계에서 수행하는 GCFD기법이 열 단위로 병렬처리하는 특성을 지니고 있으므로 첫 번째 단계에서도 열 단위의 QR-분할이 가능한 병렬 Householder updating을 이용하였다. 그 이유는 첫 번째 단계와 두 번째 단계 사이에서 발생하는 관측행렬의 병렬 전치(parallel transpose) 작업을 배제하여 통신비용을 줄일 수 있으며 이를 통하여 전체적으로 시간복잡도를 개선할 수 있기 때문이다. 제안된 기법은 반복적인 메시지 방송을 위주로 하는 통신 특성을 지니는 알고리즘이므로 메시지 방송이 가능한 구조와 분산메모리형 다중 프로세서 시스템에 적합하다.

칩의 크기가 제한된 단일칩 프로세서를 위한 레벨 1 캐시구조

주영관,김석일,Ju YoungKwan,Kim Sukil 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.2

This paper measured a proper ratio of the size of demand fetch cache $L_1$ to that of prefetch cache $L_P$ by imulation when the size of $L_1$ and $L_P$ are constant which organize space-limited level 1 cache of a single microprocessor chip. The analysis of our experiment showed that in the condition of the sum of the size of $L_1$ and $L_P$ are 16 KB, the level 1 cache organization by constituting $L_P$ with 4 KB and employing OBL and FIFO as a prefetch technique and a cache replacement policy respectively resulted in the best performance. Also, this analysis showed that in the condition of the sum of the size of $L_1$ and $L_P$ are over 32 KB, employing dynamic filtering as prefetch technique of $L_P$ are more advantageous and splitting level 1 cache by constituting $L_1$ with 28 KB and $L_P$ with 4 KB in the case of 32 KB of space are available, by constituting $L_1$ with 48 KB and $L_P$ with 16 KB in the case of 64 KB elicited the best performance. 이 논문에서는 단일 칩 프로세서에서 제한된 공간의 레벨 1 캐시를 구성하고 있는 선인출 캐시 $L_P$와 요구인출 캐시 $L_1$의 합이 일정한 때, $L_1$와 $L_P$의 크기의 적정한 비율을 실험을 통하여 분석하였다. 실험 결과, $L_1$와 $L_P$의 합이 16KB일 경우에는 $L_1$을 12KB, $L_P$를 4KB로 구성하고 $L_P$의 선인출 기법과 캐시교체정책은 각각 OBL과 FEO을 적용시키는 레벨 1 캐시 구조가 가장 성능이 우수함을 보였다. 또한 이 분석은 $L_1$와 $L_P$의 합이 32KB 이상인 경우에는 $L_P$의 선인출 기법으로는 동적필터 기법을 사용하는 것이 유리함을 보였고 32KB의 공간이 가용한 경우에는 $L_1$을 28KB, $L_P$를 4KB로, 64KB가 가용한 경우에는 $L_1$을 48KB, $L_P$를 16KB로 레벨 1 캐시를 분할하는 것이 가장 좋은 성능을 발휘함을 보였다.

슈퍼스칼라 프로세서의 자원 활용도 분석

김지선(Jisun Kim),전중남(Joongnam Jeon),김석일(Sukil Kim) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.2Ⅰ

슈퍼스칼라 프로세서 구조에서 명령어 실행을 수행하는 데 사용되는 자원은 그 양에 비해 실제로 활용된 자원의 양은 적다. 본 논문에서는 낮은 자원활용도를 보이는 자원을 활용하는 방안으로 슈퍼스칼라 프로세서를 멀티쓰레드 프로세서를 확장하는데 필요한 기본 데이터를 얻기 위해서 실제로 활용되는 자원의 양을 측정하여 어느 정도의 자원을 활용할 수 있는 지와 자원이 충분히 활용되지 못하는 원인을 분석하였다. 실험을 위해 RA(Resource Analyzer)를 구현하여 SimpleScalar 시뮬레이터에서 제공되는 명령어 파이프라인 트레이스 파일을 분석하여 각 파이프라인 단계에서 처리되는 자원의 활용도를 실험하였다. 자원 활용도가 낮은 원인을 분석하기 위해 프로그램 내에 존재하는 데이터 의존성과 여러 가지 미스 요인들의 비율을 실험을 통해 알아본 결과 IPC(Instruction Per Cycle)는 평균 0.6으로 나타났으며, EX단계의 평균 활용 빈도는 22.9%로 낮아 멀티쓰레드 처리의 필요성이 있음을 확인할 수 있었다.

Multiple - Row Downdating에서의 전처리기법의 효과

이충한(Chung-Han Lee),김석일(Sukil Kim),전중남(Joong-Nam Jun) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

본 논문에서는 기존의 Givens Downdating(GD)기법과 Hyperbolic Downdating(HD)기법을 소개하고, 새로운 downdating기법으로써 관측행렬 Z^T를 Z^T=QzR_^Tz인 상삼각행렬 R^Tz로 분할한 후 R^Yz에 GD를 적용하는 PGD기법과 HD를 적용하는 PHD기법을 제안하였다. PGD 및 PHD기법은 p≥n인 경우 각각 pn²+5n³/6 및 pn²+n³/3 flops의 시간복잡도가 필요하므로 각각 5pn²/2과 2pn² flops의 시간복잡도가 필요한 GD 및 HD기법에 비해 효과적인 downdating기법임을 알 수 있다. 벤치마크 실험에서도 PHD기법이 다른 기법에 비하여 성능이 가장 우수하였다.

스크린리더 개발 생산성 향상을 위한 개방형 API 설계

이승수 ( Seungsoo Lee ),김석일 ( Sukil Kim ) 한국정보처리학회 2005 한국정보처리학회 학술대회논문집 Vol.12 No.1

스크린리더는 그 특성상 모든 응용 프로그램을 지원해야 함에도, 타 응용 프로그램의 빈번한 업그레이드 와 스크린리더 개발 인력 부족 등의 이유로 시각장애인들이 자주 쓰는 소수의 응용 프로그램만을 지원하는 것이 현실이다. 본 논문에서는 스크린리더의 개발 생산성을 높일 수 있는 방안으로 개방형 API 를 제안한다. 스크린리더에 개방형 API 를 채택하고 이를 공개함으로써 스크린리더 개발 업체는 주엔진 모듈의 성능 향상에 모든 인력을 투입하여 성능 좋은 스크린리더을 개발할 수 있을 것이며, 프로그램 개발이 가능한 사용자나 자원봉사자들이 개방형 API 에 맞도록 응용 프로그램 지원 모듈을 플러그인 형태로 개발할 수 있을 것이다. 이를 통해 국내에서도 다양한 응용 프로그램을 지원하는 우수한 스크린 리더를 개발할 수 있을 것이다.

데이타 캐시의 활용도를 높이는 동적 선인출 필터링 기법

전영숙(Young-Suk Chon),김석일(Sukil Kim),전중남(Joongnam Jeon) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.1·2

Memory reference instructions such as loads or stores are critical factors that limit the processing power of processor. The prefetching technique is an effective way to reduce the latency caused from memory access. However, excessively aggressive prefetch leads to cache pollution so as to cancel out the advantage of prefetch. In this study, four filtering schemes have been compared and evaluated which dynamically decide whether to begin prefetch after referring a filtering table to decrease cache pollution. First, A bi-states scheme has been shown to analyze the lock problem of the conventional scheme, this scheme such as conventional scheme used to be N:1 mapping, but it has the two state to 1bit value of each entries. A complete state scheme has been introduced to be used as a reference for the comparative study. A block address lookup scheme has been proposed as the main idea of this paper which exhibits the most exact filtering performance. This scheme has a length of the table the same as the bi-states scheme, the contents of each entry have the fields the same as the complete state scheme recently, never referenced data block address has been 1:1 mapping a entry of the filter table. Experimental results from commonly used general benchmarks and multimedia programs show that average cache miss ratio have been decreased by 10.5% for the block address lookup scheme(BAL) compare to conventional dynamic filter scheme(2-bitSC). Load/store와 같은 메모리 참조 명령어는 프로세서의 고속 수행을 방해하는 주요인이다. 캐시선인출 기법은 메모리 참조에 따른 지연시간을 줄이는 효과적인 방법이다. 그러나 너무 적극적으로 선인출 할 경우에 캐시 오염을 유발시켜 선인출에 의한 장점을 상쇄시킨다. 본 연구에서는 캐시의 오염을 줄이기 위해 동적으로 필터 테이블을 참조하여 선인출 명령을 수행할 지의 여부를 결정하는 네 가지 필터링 기법들을 비교 평가한다. 먼저 기존 연구에서의 문제점을 분석하기 위해 이진 상태 기법을 보였는데, 이 기법은 기존 연구와 같이 N:1 매핑을 사용하는 반면, 각 엔트리의 값을 1비트로 하여 두 가지 상태값을 갖도록 하였다. 비교 연구를 위해 완전 상태 기법을 제시하여 비교 기준으로 사용하였다. 마지막으로 본 논문의 주 아이디어인 정교한 필터링을 위한 블록주소 참조 기법을 제안하였다. 이 기법은 이진 상태 기법과 같은 테이블 길이를 가지며, 각 엔트리의 내용은 완전 상태 기법과 같은 항목을 가지도록 하여 최근에 미사용된 데이타의 블록주소가 필터 테이블의 하나의 엔트리와 대응되도록 1:1 매핑을 하였다. 일반적으로 많이 사용되는 일반 벤치마크 프로그램과 멀티미디어 벤치마크 프로그램들에 대하여 실험한 결과, 제안한 블록주소 참조 기법(BAL)이 기존 연구인 동적 필터 기법(2-bitSC)과 비교하여 캐시 미스율이 10.5%감소하였다.