그래프 감축기 상에서 구현된 효과적인 세대별 쓰레기 수집 정책

한상영(Sangyong Han),배종민(Jongmin Bae) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.9

세대별 쓰레기 수집 정책은, 원래의 정지/복사 알고리즘에 비하여, 수명이 긴 객체가 많을 때는 프로그램 전체를 수행 완료하기 까지의 걸리는 시간을 단축시킬 수 있지만, 수명이 짧은 객체가 많을 경우가 그 시간이 절약되지 않는다는 연구 결과가 있다. 또한 기존의 세대별 복사 알고리즘에서는, 객체의 세대 이동으로 인하여, 수집 작업 도중에 다음 세대의 영역이 가득 차게되는 상황이 발생할 수가 있어서, 이때는 그 처리가 어렵고, 수집 작업의 효율이 매우 떨어질 수 있다. 본 논문은 이러한 문제점을 해결하는 세대별 쓰레기 수집 정책에서의 새로운 메모리 관리 모델을 제시한다. 그리고 객체 수명의 개념을 쓰레기 수집기 입장에서 재 조명해서, 이를 바탕으로 세대별로 수집이 일어나는 시기를 동적으로 조절해서 최적의 수집 시기를 결정하는 경험적 정책을 제시한다. 제시된 모델은 그래프 감축기 상에서 구현되었으며, 이에 대한 성능 평가를 보인다. In comparison with stop-and-copy collectors, generational garbage collectors are expected to perform better for programs with a large amount of long-lived objects, but not for programs with a small amount of long-lived objects and a large amount of short-lived objects. And because of promotion of objects, the next generation space can be full before finishing the collection. That situation is difficult to be resolved, and efficiency of garbage collection algorithm can be degraded. This paper proposes the new memory management policy to cope with these problems, and proposes the heuristics to determine the optimal collection time for each generation from the observations for the concept of lifetime of objects from a standpoint of the garbage collection. The proposed algorithm is implemented on a graph reduction machine, and the results are given.

다중 스레드 구조상에서 객체지향 함수형 언어 구현

장준호(Juno Chang),한상영(Sangyong Han) 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.12

객체지향 함수형 언어는 병렬 컴퓨터 상에서 실행될 수 있는 응용 프로그램의 범위를 넓혀주는 반면, 병렬 프로그램의 작성을 쉽도록 하는 병렬 프로그래밍 언어이다. 객체지향 함수형 언어는 함수형 언어와 객체지향 언어의 장점을 결합하여, 재사용이 가능하면서 최대한의 병렬성 표현이 가능한 코드를 작성할 수 있으며, 다중 스레드 구조상에서 효과적으로 수행될 수 있다. 본 논문에서는 다중 스레드 구조상에서 병렬 프로그래밍 언어로 활용되고 있는 함수형 언어인 Id에 객체지향 개념을 혼합한 객체지향 함수형 언어, OOId를 제안하고, 이를 다중 스레드 구조인 DAVRID상에서 효과적으로 실행시키기 위한 구현 기법을 제안하였다. 또한 부가된 객체지향 개념이 실행시간에 미치는 영향을 분석하였다. Object-oriented Functional language is an implicitly parallel programming language designed to allow a wide range of applications to be implemented on parallel machines while simplifying parallel programming for programmers. Object-oriented functional language combines the advantages of functional and object-oriented programming language, to express maximum parallelism and write reusable programs. This paper proposes an implementation technique of object-oriented functional language on the multithreaded architecture, DAVRID, and analysis of the result. We suggest a new object-oriented functional language, OOId, which expands the functional language, Id, with object-oriented concepts.

다중스레드 구조에서 자료 구조의 지역성을 이용하기 위한 IB-구조

김윤호(Yoonho Kim),한상영(Sangyong Han) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.7

최근에는 컴퓨터 구조의 스펙트럼상에 양 극단에 위치하는 폰 노이만 컴퓨터 구조와 데이타플로우 컴퓨터 구조의 장점들을 적절히 결합한 다중스레드 구조에 대한 연구가 활발히 진행중이다. 다중 스레드 구조는 스레드내에서 계산의 지역성을 이용하고 스레드들간의 비동기적 병렬수행을 통해 성능 향상을 추구 한다. 그러나 스레드들간에 공유되는 큰 규모의 자료 구조에 대해서 지역성을 효과적으로 이용하는 연구는 상대적으로 간과되어져 왔다. 본 논문에서는 대부분의 데이타 플로우 컴퓨터와 다중 스레드 컴퓨터에서 자료구조로 사용하는 I-구조를 자료구조의 지역성을 효과적으로 이용하기 위하여 확장된 IB 구조를 제안하고, 이를 다중스레드 구조인 DAVRlD(DAtaflow Von Neumann RISC hybrID)시스템에서 구현하였다. 시뮬레이션을 통한 성능 분석 결과, 여러 벤치마크에 대해 IB-구조가 I-구조보다 우수하다는 점을 보였다. Multithreaded architectures, taking a hybrid approach of von Neumann computers and dataflow computers, are in active research. Multithreaded architectures can improve the the performance by exploiting the locality within a thread and supporting asynchronous parallel execution among threads. However, it has been overlooked how to exploit effectively the locality of large shared data structures among threads in multithreaded architectures. A new data structure called IB-structure, which is an extension of I-structure to facilitate the distribution of data structure and exploit the spatial and temporal locality of data structure, is proposed in this paper. We have implemented it on DAVRID(DAtafiow Van Neumann RISC hybrID)system based on the multithreaded architecture. The simulation results show that IB-structure is superior to I -structure over several benchmarks.

비정형성 함수 언어를 위한 향상된 스레드 형성 기법

하상호(Sangho Ha),한상영(Sangyong Han),김흥환(Heunghwan kim),김수홍(Soohong Kim) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.12

다중스레딩은 전역 메모리 참조등 긴 지체시간을 초래하는 연산을 분할하여 수행토록 하고, 프로세서의 유휴시간을 초래하지 않고서 계산들간에 빠른 문맥 교환을 가능하게 함에 따라 대규모 병렬 시스템에 매우 효과적이다. 다중스레드 컴퓨터의 성능은 다중스레드 코드의 질의 좌우된다. 본 논문은 비정형성 함수 언어 Id￣[1]로 작성된 프로그램으로부터 효율적인 다중 순차 스레드를 생성하는 향상된 스레드 형성 기법을 제안한다. 이 스레드 형성 기법은 긴 지체시간을 초래하는 명령어에 기준한 데이타플로우 프로그램 그래프의 분할, 일반화된 스위치와 합병 노드의 새로운 도입을 통한 여러 스위치와 합병 노드의 결합, 스레드 선행 관계에 기반한 스레드 합병 및 중복된 아크 제거 등의 특징을 갖는다. 시뮬레이션을 통해 스레드의 합병과 중복 아크 제거의 효과를 분석하고, 제안된 스레드 형성 기법과 Schauser[2]의 기법을 비교한다. 시뮬레이션 결과는 본 논문의 기법이 다중스레딩의 부담인 코드의 제어 부분과 branch 명령어를 효과적으로 감소하고 있음을 보여준다. Multithreading is attractive for a large-scale parallel system since it allows long latency instructions to be dealt with as split-phase transactions as well as fast context switching between computations without blocking the processor. Performance of multithreaded architectures depends significantly on the quality of multi-threaded codes. In this paper, we describe an enhanced thread formation scheme to produce efficient sequential threads from programs written in a non-strict functional language Id￣ [1]. This scheme features dataflow program graph partitioning based on only long latency instructions, combination of switch and merge introducing a generalized switch and merge, thread merging and redundant arc elimination using thread precedence relation. We analyze the effect of thread merging and redundant arc elimination, and compare our scheme with Schauser's[2] through simulation. Simulation results show that our scheme reduces the control portion of codes, which is overheads due to multithreading, and branch instructions effectively.

폰 노이만 구조를 채택한 데이타플로우 다중스레드 컴퓨터

김정환(Junghwan Kim),한상영(Sangyong Han),김수홍(Soohong Kim) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.9

다중스레드 방식은 병렬 처리의 기본 문제인 지연 시간과 동기화 문제의 해결에 효과적이다. 다중스레드 컴퓨터 DAVRID는 데아타플로우 모델에 폰 노이만 모델의 장점을 흡수한 계산 모델을 취하고 있다. 본 논문에서는 성능 분석을 통해 DAVRID의 문제점을 제시하고, 새로운 컴퓨터 구조 MVA(Dataflow Multithreaded Computer Organization with Von Neumann Architecture)를 제안한다. DAVRID는 계산 모델 측면에서 지연 시간과 동기화 문제의 해결에 매우 효과적이지만, 구조적으로는 지역성 활용에 어려움이 있다. 제안된 MVA는 DAVRID의 계산 모델은 그대로 유지하면서 기존의 일반적인 폰 노이만 구조를 채택함으로써, 효율적인 병렬 처리를 꾀하고 있다. MVA에 대한 성능 분석 결과, DAVRID에 비해 처리 시간이 대폭 감소하였으며, 각 장치의 이용률이 증가하면서 이용률 편차가 감소하였다. Multithreading is effective to solve the latency and the synchronization problem which are one of fundamental issues in parallel processing. One of multithreaded computers, DAVRID has the computational model which is based on the dataflow model together with the advantages of the van Neumann model. In this paper, we analyze some problems of the DAVRID through performance evaluation and propose a new architecture, called MVA(Dataflow Multithreaded Computer Organization with Von Neumann Architecture). The DAVRID effectively solves latency and synchronization problems from the view point of computational model, but has difficulty in exploiting locality from the view point of the architecture. The MVA pursuits efficient parallel processing in the way it inherits the computational model of thc DAVRID and has conventional van Neumann architecture. Simulation results show that the execution time of the MVA is significantly reduced compared with that of the DAVRID, and the high variance of utilization among units is also reduced while overall utilization is increased.

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

김정환(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.

다중 스레드 구조 컴퓨터에서 재귀 함수의 실행을 위한 프레임-토큰 기반 병렬성 제어

이대웅(Daewoong Rhee),조태희(Taehee Cho),한상영(Sangyong Han) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.2

프레임-기반 다중스레드 구조에서 재귀 함수에 내재한 병렬성을 최대한 이용하기 위해서는 많은 프레임 메모리를 필요로 한다. 과도한 병렬성은 적절히 제어되지 않으면 메모리 용량의 한계를 넘어서는 실행을 요구할 수도 있으며, 프로그램을 교착 상태에 이르게 할 수도 있다. 본 논문에서는 프레임-토큰 개념을 도입하여 동시에 할당될 수 있는 프레임의 수를 제안함으로써 병렬성의 이용을 자원의 한계내에서 유지하면서 재귀 함수를 효과적으로 실행하는 프레임-토큰 기반 병렬성 제어 기법을 제안한다. 제안한 기법을 프레임-기반 데이타플로우 다중스레드 구조인 DAVRID의 실행 시간 시스템에 메시지 전달 방식으로 구현한다. 시뮬레이션을 통해 제안한 방법이 병렬성 제어를 하지 않았을 때는 실행하기 어려운 재귀 함수에 대해서도 효과적으로 실행함을 보인다. One of the principal problems in frame-based multithreaded architectures is the control of parallelism for highly parallel programs. If the excessive parallelism inherent in recursive functions is not controlled, then it could require resources beyond the limit of frame memory capacity and might lead to a resource deadlock. The challenge is to control the parallelism without reducing the machines' ability to exploit it. In this paper, a frame-token based parallelism control method for the execution of recursive functions in DAVRID is proposed. The notion of frame-token is introduced to constrain the amount of frames which can be allocated to processors. The proposed method is implemented on the run time system of DAVRID which is frame-based dataflow multithreaded architecture. Simulation results show that the frame-token based parallelism control method can execute effectively the recursive programs, which are difficult to be executed without controlling the parallelism, at the cost of msignificantly increased execution time.

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

하상호(Sangho Ha),김흥환(Heunghwan Kim),한상영(Sangyong Han) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.6

다중스레딩은 기존의 병렬 컴퓨터의 확장성에 커다란 장애 요소인 메모리 참조의 긴 지체시간과 동기화의 문제[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 computers. 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-unfolding 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.

다중스레드 구조에서 병렬 객체지향 계산을 위한 효과적인 실행시간 모델

송종훈(Jonghoon Song),김흥환(Heunghwan Kim),한상영(Sangyong Han) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.11

객체지향 기법은, 사용자가 각 객체를 병렬로 실행되는 메시지 전달 장치로 다룰 수 있는 환경을 제공하기 때문에, 병렬 및 분산시스템에서 효과적으로 이용될 수 있는 패러다임이다. 그러나, 다중스레드 구조에 기초한 객체지향 환경은 빈번한 프레임의 할당 요청으로 인해서, 다른 계산 환경에 비해 메시지 교환량에 따른 오버헤드가 크다. 본 논문에서는 다중스레드 구조에 기반을 두고 있는 객체 지향 시스템 OOId/DAVRID에서 객체지향 계산의 성능을 향상시킬 수 있는 실행시간 모델을 제안한다. 이 모델은 클래스 상속을 효과적으로 지원하며, 메시지 오버헤드를 줄이기 위해서 기존의 객체 프레임 할당과 멤버 함수 호출을 개선하였으며, 변경 가능한(mutable) 멤버를 효과적으로 접근하도록 하였다. 성능분석의 결과는 제안된 모델이 기존의 모델보다 성능이 우수함을 보여준다. 그리고, 그 성능 향상의 정도는 많은 객체가 동적으로 생성되어 객체 관련 메시지가 빈번한 응용에서 더 크게 나타남을 확인할 수 있었다. The object-oriented paradigm is ideal for parallel and distributed systems, because users can naturally treat an object as the message-passing unit which is executed concurrently. But, in the object-oriented environment based on multithreaded architecture, the message traffic is heavier than in other environments because of the frequent requests for frame allocation We suggest a runtime model on object-oriented system OOId/DAVRID, which can improve the performance of object-oriented computing in multithreaded architecture. This model supports class inheritance efficiently and improves the object frame allocation and member function call to reduce the message overhead. It also allows efficient access to the mutable member. The simulation results show that the proposed model is superior to a previous model in performance and the performance gain is larger in the application where many objects are dynamically created.

다중스레드 계산 모델을 이용한 병렬 객체지향 프로그래밍 환경의 구현 및 성능 평가

송종훈(Jonghoon Song),김흥환(Heungwan Kim),한상영(Sangyong Han) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.6

본 논문에서 제안하는 시스템은 일반적인 병렬 시스템의 하드웨어 구조에서, 다중 스레드 계산 모델을 이용하여 객체 지향 프로그래밍 환경을 구현한 시스템이다. 제안하는 시스템을 효과적으로 구현하기 위하여 컴파일러와 실행 시간 시스템의 측면에서 여러 가지 기법을 제시한다. 컴파일러의 측면에서는 멤버 변수의 접근 분석, 메소드의 병렬성 분석 기법을 제시하고, 실행 시간 시스템에서는 실시간 스레드/메시지 결합, 프레임 공유 기법을 제시한다. 본 논문에서 제안된 프로그래밍 환경은, MPI 메시지 인터페이스를 이용하여 구현하였으며, 벤치마크 프로그램을 실행함으로써 성능 분석을 하였다. 분석의 결과는 실행시간 시스템의 여러 가지 기법들이 성능 향상에 많은 효과가 있음을 보여주며, 이러한 결과는 일반적인 병렬 시스템에서도 적용 가능하다. In this paper, we suggest an object-oriented programming environment with multithreaded computation model on general parallel processing systems. We developed many methods for our environment to be efficient. in complier, the analysis of member variable and method parallelism, and in runtime system, thread/message merging and frame sharing. The programming environment is implemented with MPI message interlace, and its performance is analyzed with executing benchmark programs. The results show that the developed methods have influence on performance improvement, and this improvement can be applied to general parallel processing systems.