다중스레드 컴퓨터에서 루프의 효율적인 구현 방법

김흥환(Heunghwan Kim) 서원대학교 미래창조연구원 1998 응용과학연구 Vol.7 No.1

데이타 병렬 프로그램에서 루프 세부 분할 및 동적 스케쥴링을 통한 통신과 계산의 중첩 모델

김정환(Junghwan Kim),한상영(Sangyong Han),조승호(Seungho Cho),김흥환(Heunghwan Kim) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.1

본 논문은 데이타 병렬 프로그램에서 효율적 통신을 위한 하나의 방법으로 통신과 계산 작업을 중첩하여 실행하는 모델을 제안한다. 이 중첩 모델에서는 통신 지연 시간 동안 중첩하여 수행할 계산작업을 얻기 위해 주어진 루프 분할을 다시 세부 분할한다. 주어진 루프 분할은 다른 외부 데이타 분할을 참조하기도 하지만, 루프 분할의 모든 반복들이 항상 외부 데이타 참조를 필요로 하는 것은 아니다. 따라서 주어진 루프 분할을 외부 데이타를 요구하는 루프 반복들의 집합과 그렇지 않은 루프 반복들의 집합으로 나눌 수 있다. 이렇게 나누어진 루프 세부 분할은 효율적인 수행을 위해 메시지 도착 순서에 따라 동적으로 스케쥴링된다. 제안된 방법에 따라 IBM SP2에서 몇가지 프로그램으로 실험을 한 결과, 중첩 모델이 성능 향상을 보임을 확인할 수 있었다. We propose a model which overlaps communication with computation for efficient communication in the data-parallel programming paradigm. The overlapping model divides a given loop partition into several sub-partitions to obtain computation which can be overlapped with communication. A loop partition sometimes refers to other data partitions, but not all iterations in the loop partition require non-local data. So, a loop partition may be divided into a set of loop iterations which require non-local data, and a set of loop iterations which do not. Each loop sub-partition is dynamically scheduled depending on associated message arrival. The experimental results for a few benchmarks in IBM SP2 show enhanced performance in our overlapping model.

다중스레드 컴퓨터상에서 비정형성 함수 언어의 효과적인 루프 펼침 기법

김흥환,한상영,하상호 서원대학교 응용과학연구소 1996 응용과학연구 Vol.5 No.1

다중스레딩은 기존의 병렬 컴퓨터의 확장성에 커다란 장애 요소인 메모리 참조의 긴 지체시간과 동기화의 문제[1]를 효과적으로 해결할 수 있다는 점에서 많은 관심을 얻고 있다. 그러나 다중스레드 컴퓨터에 루프내 병렬성을 사상하는 기법에 관한 연구는 매우 미흡하다. 본 논문에서는 미세한 수준의 대규모 병렬성을 표현할 수 있는 비정형성 함수 언어 Id-[2]의 루프 구문을 다중스레드 컴퓨터상에 효과적으로 구현할 수 있는 루프 펼침 기법을 제안한다. 루프는 그 본체내 반복간의 종속 여부에 따라 순차 혹은 병렬 루프로 구분될 수 있다. 제안된 기법은 루프 종류에 따라 효과적으로 적용할 수 있도록 K-펼침 순차 루프와 K-펼침 병렬 루프는 구성된다. DAVRID 컴파일러[2]에 구현된 이 기법은 시뮬레이션을 통해 여러 벤처마크에 대해서 실험되었으며, 실험 결과로부터 루프 펼침 효과를 분석할 수 있다. Multithreading is very attractive in that it can solve effectively two fundamental problems[1]. memory latency and synchronization, which are obstacles to the scalarbility of existing parallel computers. However, it has been overlooked how to map parallelism in loops to multithreaded computer. In this paper, we present a loop unfolding scheme to implement loops effectively in Id[2], which is a nonstrict functional language, on multithreaded computers. Loops can be classified into sequential or parallel loops, depending on existence of loop carried dependencies in their bodies. Our scheme includes K-unfolding sequential loop and K-unifolding parallel loop which can be applied effectively according to the class of loops. The scheme was implemented in the DAVRID compiler[2]. We analyzed the effect of loop unfolding by simulating it over several benchmarks.

WBI 자료의 유형과 개발 방법에 대한 연구

김흥환 서원대학교 교육대학원 2002 교육논총 Vol.6 No.-

The development of ICT(Information Communication Technology) and Internet technology changed the traditional educational system. The change is under way and will be continued. The terms, open education, lifelong education, and cyber education are nothing new. The educational system of university is never free from the change. WBI(Web Based Instruction) is a spotlighted educational method using WWW(World-Wide-Web) technologies for education. In this paper, we present the types and development methods of WBI material. First, we explain the types of WBI material in view of instructional strategies. Secondly, we explain a development system and tools for good WBI material development. Thirdly, we discuss a team approach for systematic WBI material development. Finally, we present a development system suitable for our university and conclude with the remarks on future educational system.

다중스트레드 컴퓨터에서 루프의 효율적인 구현 방법

김홍환 서원대학교 응용과학연구소 1998 응용과학연구 Vol.7 No.1

Multithreading is attractive in that it can solve two fundamental problems, latency and synchronization, for scalable parallel computers, by overlapping communication and computation. While several compiler techniques have been developed to produce multithreaded codes from functional programs, we can hardly find effective implementation schemes for the multithreaded environment. In this paper, we will suggest an efficient loop unfolding scheme, KU-Loop for multithreaded computation. In this scheme, parallel loops can be implemented more efficiently than sequential loops by effectively overlapping loop set-up with loop execution. Additionally, we will suggest the eqauations to statically approximate the optimal loop unfolding degree for each loop class: parallel and sequential loops. Simulation results showed that our method is very effective.

사이버 교육 시스템에서 지능형 에이전트의 적용에 관한 연구

김흥환 서원대학교 교육대학원 2003 교육논총 Vol.7 No.-

Agent is a person or thing that acts on behalf of someone or something. Software agent is a computing entity that performs user delegated tasks autonomously. Agents are very effective in the areas of E-commerce, manufacturing, process control, telecommunications, air traffic control, transportation systems, information management, business process management, games, interactive theatre and cinema, patient monitoring, health care, and so on. In this paper, we propose a cyber education system using agent technologies. Agent technologies make it possible to smooth the interactions between learners and cyber education system and support the self-directed learning more effectively.

웹 프로그래밍 교육을 위한 WBI 자료 개발

김흥환 서원대학교 응용과학연구소 2002 응용과학연구 Vol.11 No.1

The advance of computer, communication, and Internet technologies changed the traditional educational system. The change is under way and will be continued. WBI(Web Based Instruction) is a spotlighted educational method using WWW(World-Wide Web) technologies for education. Web Programming is one of very important topics for computer scientists and engineers. We developed WBI material for education of the subject, Web Programming. We used this material in classroom at last semester via HCU(Han Cyber University), which is a consortium of universities at Chungchung province for cyber education. We observed that it was effective. Students accessed it frequently and shared much useful information via bulletin board of HCU.

A Non-Strict Data Access Model for Multithreaded Loop Execution

Eunha Rho,Sangyong Han,Heunghwan Kim 대한전기학회 2000 Journal of Electical Engineering and information S Vol.5 No.3

다중스레딩 실행 방식에 의한 Id 함수 언어의 반복 구문 실행 기법 비교

하상호(Sangho Ha),김흥환(Heunghwan Kim),한상영(Sangyong Han) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.5

다중스레딩(multithreading)은 긴 메모리 지체 시간과 동기화의 문제점을 해결할 수 있다는 점에서 대규모 병렬 기계 구조에 매우 적합하다. 함수 언어 Id를 다중스레딩 방식으로 실행시키기 위한 여러 연구가 이루어져 왔으나, 반복 구문에 관한 연구는 아직 미흡하다. 본 논문에서는 다중스레드 구조상에서 반복 구문의 세 가지 실행 방식, 즉 재귀 함수, K-펼침 루프, 루프 순차화를 비교한다. 특히, 논문에서 제안된 루프 순차화 방식에서는 다른 두 방식과는 달리, 루프의 모든 반복을 순차적으로 실행시킨다. 시뮬레이션의 분석 결과는 병렬성이 적고, 복잡한 자료 종속을 갖는 루프에 대해서 루프 순차화의 방식이 다른 두 방식보다 매우 효과적임을 보여준다. Multithreading is attractive for massively parallel architectures in that it can tolerate long memory latencies and synchronization overheads. Although several methods to execute Id programs by multithreading have been studied, the efficient implementation method of its iteration constructs has been nearly ignored In this paper, we compare three schemes of loop execution: recursion, k-unfolding loop, and loop sequentialization. Especially, loop sequentialization presented in this paper executes all iterations sequentially unlike other this schemes that unfold loops. The simulation analysis shows that loop sequentialization is very effective for loops with small computation and complicated data dependencies in their bodies.

명령형 프로그램의 데이타플로우 프로그램 그래프로의 변환

나윤희(Yoonhee Nah),김흥환(Heunghwan Kim),한상영(Sangyong Han) 한국정보과학회 1995 정보과학회논문지(B) Vol.22 No.10

데이타플로우 프로그램 그래프는 데이타플로우나 다중스레드 모델에 기반을 두고 있는 병렬 컴퓨터 시스템에서 많이 사용되는 중간 표현으로, 기계 독립적이며 다양한 형태와 수준의 병렬성을 자연스럽게 표현한다. 본 논문에서는 기본 블럭의 특성과 프로그램 그래프의 은닉기 명령문의 특성을 이용함으로써 복잡한 분석 과정과 중간 표현 단계를 거치지 않고 명령형 프로그램을 프로그램 그래프로 변환하는 방법인 추상화 방법(Abstract Method)을 제시한다. 추상화 방법은 우선 기본 블럭의 특성을 이용하기 위해 원시 프로그램을 단순 실행문과 추상 실행문으로 구성되는 계층 구조 코드(HSC: Hierarchically Structured Code)로 변환한다. 다음에 이를 프로그램 그래프로 변환하는데, 추상 실행문은 인자로 사용된 하위 계층 구조 코드들의 입출력 조정을 통해 프로그램 그래프의 은닉기 명령문으로 변환된다. Many parallel computer systems which are based on dataflow or multithread models have used the dataflow program graph as an intermediate representation. This paper presents a method. called the Abstract Method. in Which imperative programs are transformed into program graphs without several intermediate forms and complex analysis because it exploits characteristics of basic blocks and encapsulator instructions of program graph. In the Abstract Method. first, to exploit characteristics of basic blocks, source programs are transformed into Hierarchically Structured Codes(HSCs), which consist of simple statements and abstract statements Next, HSCs are transformed into program graphs. During this transformation, each of abstract statements is transformed into an encapsulator instruction of program graph through tuning inputs and outputs of subordinate HSCs.