재겨냥성 C 컴파일러를 위한 테스트 집합 생성 시스템

우균,배정호,장한일,이윤정,채흥석,Woo, Gyun,Bae, Jung-Ho,Jang, Han-Il,Lee, Yun-Jung,Chae, Heung-Seok 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.4

임베디드 프로세서 사용이 증가함에 따라 임베디드 프로세서를 위한 컴파일러를 시기 적절히 개발해야 할 필요성이 증가하고 있다. 컴파일러 후단부를 수정하여 새로운 컴파일러를 구성하는 재겨냥 기법이 이에 적합한 기법으로 채택되고 있다. 이 논문에서는 재겨냥성 C 컴파일러를 테스트하기 위한 테스트 집합 생성 시스템을 제안한다. 제안한 시스템은 문법 커버리지 개념을 이용하여 테스트 집합을 생성한다. 일반적으로 원시 프로그래밍 언어의 문법을 이용하여 테스트 집합을 생성하면 방대한 크기의 테스트 집합이 얻어진다. 그러나 신속히 컴파일러를 출시해야하는 상황에서는 방대한 테스트 집합 크기가 문제가 될 수 있다. 이에 이 논문에서 제안한 시스템은 중간 코드를 고려하여 테스트 집합을 축약하는 기능을 탑재하고 있다. 실험 결과에 따르면, 비록 축약된 테스트 집합 크기는 원본 테스트 집합 크기의 평균 10%에 불과하지만 원본 테스트 집합이 검출할 수 있는 컴파일러 오류의 75% 정도를 검출할 수 있음을 알 수 있었다. 이는 본 논문에서 제시한 축약 기법이 임베디드 컴파일러 개발 초기 단계에서 효과적으로 사용될 수 있음을 의미한다. With the increasing adoption of embedded processors, the need of developing compilers for the embedded processors with timely manner is also growing. Retargeting has been adopted as a viable approach to constructing new compilers by modifying the back-end of an existing compiler. This paper proposes a test suite generation system for testing retargetable C compilers. The proposed system generates the test suite using the grammar coverage concept. Generally, the size of the test suite satisfying the grammar coverage of the source language is very large. Hence, the proposed system also provides the facility to reduce the size of the test suite. According to the experimental result, the reduced test suite can detect 75% of the compiler faults detected by the original test suite though the size of the reduced test suite is only 10% of that of the original test suite in average. This result indicates that the reduction technique proposed in this paper can be effectively used in the prior phase of the development procedure of the embedded compilers.

클래스 멤버 사이의 쓰기 연산을 고려한 새로운 TCC 및 LCOM 척도

우균(Gyun Woo),채흥석(Heung Seok Chae) 한국정보과학회 2005 정보과학회논문지 : 소프트웨어 및 응용 Vol.32 No.11

응집도는 모듈의 구성 요소들 사이의 관련성 정도를 나타내는 척도로서, 응집도가 높을수록 소프트웨어에 대한 이해 및 유지보수가 용이하다고 알려져 있다. 최근에 응집도의 개념을 객체지향 시스템의 클래스에 적용하기 위하여 많은 응집도 척도들이 제안되고 있다. 본 논문에서는 클래스 멤버 간의 쓰기 의존성의 영향을 고려함으로써 기존의 응집도 척도를 개선시킬 수 있음을 소개한다. 본 논문의 기법을 지원하는 도구를 개발하였으며 이 도구를 이용하여 C++ 클래스 라이브러리에 이 기법을 적용한 사례 결과를 소개한다. Cohesion refers to the degree of the relatedness of the members in a class and it is widely accepted that the higher the cohesion of a module is, the easier the module to understand and maintain. Recently, several cohesion measures have been proposed to measure the cohesiveness of classes in an object-oriented program. In this paper, we propose an approach to improving the existing cohesion measures by considering the impact of write dependencies between class members. We have developed a cohesion measurement tool for supporting our approach and describe a case study performed with a C++ class library.

ZG-machine을 위한 비재귀적 메모리 재사용

우균(Gyun Woo) 한국정보과학회 프로그래밍언어연구회 2000 프로그래밍언어논문지 Vol.14 No.1

태그 옮기기에 의한 G-machine 그래프의 압축

우균(Gyun Woo),한태숙(Taisook Han) 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.5

지연 함수형 언어를 효율적으로 구현하기 위한 한 방법으로 G-machine이 제안되었다. G-machine은 그래프 축약을 빠르게 수행하지만, 축약 과정의 그래프를 저장하기 위해 많은 기억장소를 필요로 한다. 이는 그래프 축약 방법 자체의 문제점으로 생각된다. 이 논문에서는 그래프 노드의 태그를 옮김으로써 기억장소의 그래프 구조를 압축할 수 있는 방법을 제안한다. 노드의 태그는 그 노드를 가리키는 포인터 자리로 옮겨지는데, 포인터 정보를 유지하기 위해 상대주소와 합쳐져 함께 옮겨진다. 태그 옮기기는 그래프 구성 노드를 힙에 동시에 할당할 수 있을 때 가능하다. 그러나, 일반적으로 그래프의 일부가 전체 그래프가 생성되기 이전에 생성될 수 있으므로, 이러한 태그 옮기기가 항상 가능한 것은 아니다. 그렇지만, 태그 옮기기에 의해서 어느 정도의 힙 사용량을 줄일 수 있다. 태그 옮기기에 의해 그래프를 압축했을 때, 압축된 그래프를 해석하기 위한 수행 시간의 부담이 생기게 되는데, 이 부담 정도를 알아보기 위해 몇몇 작은 프로그램에 대해서 실험 결과를 보였다. 실험 결과에 따르면, 태그 옮기기를 수행한 결과, 총 힙 사용량은 평균 약 30% 감소하였고, 이로 인한 수행 시간 부담은 원래의 G-machine과 비슷한 수준인 것으로 나타났다. G-machine is an efficient implementation of lazy functional languages. It is a fast way to perform the graph reduction. However, it needs a lot of space to store the graphs, which seems an inherent deficiency of graph reduction. In this paper, we propose a way to compress the graphs by forwarding the tag of a graph node to the location of a pointer to the node. A tag is forwarded with a relative address, which is used to find the location of data fields of the node. The tag-forwarding is possible only when a graph is allocated at once. Hence, it cannot be applied when some nodes are allocated before the construction of the whole graph. Nonetheless, we can reduce the heap usage to a certain amount by applying the tag-forwarding to the parts of a graph which are allocated at once. The overhead of decoding the tag-forwarded graphs is imposed on at run-time. To estimate the overhead, some experiments are performed. According to the experimental results, the total heap space used is reduced about 30% on average and the run-time overhead of decoding is comparable to the original G-machine.

ZG-machine에서 기억 장소 재활용 체계의 영향

우균(Gyun Woo),한태숙(Taisook Han) 한국정보과학회 2000 정보과학회논문지 : 소프트웨어 및 응용 Vol.27 No.7

ZG-machine은 태그옮김이라는 간단한 부호화 기법을 채택한 공간 효율적인 G-machine이다. 기억 장소 재활용 체계 없이 실험한 이전 실험에서 ZG-machine은 G-machine과 비교하여 30%의 힙 공간을 절약할 수 있었고 수행 시간 부담은 6%를 넘지 않았었다. 이 논문에서는 ZG-machine에 기억 장소 재활용 체계를 장착하여 추가로 실험한 결과를 설명한다. 결과에 따르면, G-machine과 비교할 때, ZG-machine의 수행 시간은 34% 증가하였지만 최소 힙 사용량은 평균 34% 감소하였다. 수행 시간 부담이 커진 이유는 기억 장소 재활용 체계때문이다. 그러나 힙 공간을 최소 힙 사용량의 7 배 정도로 늘렸을 경우에 G-machine에 대한 수행 시간 부담은 12%를 넘지 않았다. ZG-machine에서 최소 힙 사용량이 줄어든 특성은 ZG-machine이 내장 체계와 같은 기억 장소가 제한된 응용 분야에 사용될 수 있음을 의미한다. 또한 보다 효율적인 기억 장소 재활용 쳬계를 개발함으로써 수행 시간은 상당히 줄어들 것으로 예상 된다. The ZG-machine is a space-efficient G-machine, which exploits a simple encoding method, called tag-forwarding, to compress the heap structure of graphs. Experiments on the ZG-machine without garbage collection shows that the ZG-machine saves 30% of heap space and the run-time overhead is no more than 6% than the G-machine. This paper presents the results of further experiments on the ZG-machine with the garbage collector. As a result, the heap-residency of the ZG-machine decreases by 34% on average although the run-time increases by 34% compared to the G-machine. The high rate of the run-time overhead of the ZG-machine is incurred by the garbage collector. However, when the heap size is 7 times the heap-residency, the run-time overhead of the ZG-machine is no more than 12% compared to the G-machine. With the aspect of reduced heap-residency, the ZG-machine may be useful in memory-restricted environments such as embedded systems. Also, with the development of a more efficient garbage collector, the run-time is expected to decrease significantly.

AMOS - 메뉴 방식에 의거한 객체 지향 데이타베이스 스키마 디자이너

우균(Gyun Woo),박종목(Chong-Mok Park),심재균(Jae-Kyun Shim),황규영(Kyu-Young Whang) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2

본 논문에서는 C++를 데이타 언어로 하는 객체 지향 데이타베이스 시스템을 위한 스키마 디자이너의 설계와 구현을 기술한다. 스키마 디자이너의 기능은 두 가지로 구분된다. 하나는 사용자가 효과적으로 데이타베이스 스키마를 설계할 수 있도록 하는 것이고, 다른 하나는 설계된 스키마를 응용 프로그램 개발 과정에서 이용할 수 있는 형태로 변환해 주는 것이다. 본 논문에서 기술한 스키마 디자이너는 윈도우 방식의 시각적 인터페이스로 스키마 설계를 지원하며, C++해더 화일을 생성해 줌으로써 응용 프로그램 인터페이스를 지원한다.

공간 조정을 이용한 복사 메모리 재사용 알고리즘

우균(Gyun Woo),김성청(Soung-Choung Kim),주성용(Sung-Yong Joo),차미양(Mi-Yang Cha),한태숙(Tae-Sook Han) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅰ

이 논문은 메모리 재사용 알고리즘 중 하나인 복사 알고리즘의 공간 오버헤드를 완화시키기 위한 방법을 기술한다. 복사 알고리즘은 연속적인 메모리 공간을 확보하는 전통적인 메모리 재사용 알고리즘으로, 노드 크기가 일정하지 않은 추상 기계의 구현에 널리 사용되는 알고리즘이다. 그러나, 복사 알고리즘은 전체 힙 공간의 반을 복사 프로세스를 위해서 남겨두어야 하기 때문에 공간 오버헤드는 100%에 달한다. 이 논문에서는 공간 오버헤드를 완화시키는 기본 아이디어를 제시하고, 이 기본 아이디어에서 힙 경계 부분을 처리하기 위한 세 가지 방법을 제안한다.

임베디드 시스템을 위한 실시간 함수형 반응적 프로그램 변환기

이동주,우균,Lee, Dong-Ju,Woo, Gyun 한국정보처리학회 2006 정보처리학회논문지 A Vol.13 No.6

함수형 반응적 프로그래밍(FRP: Functional Reactive Programming)은 하스켈(Haskell)에 내장된 언어로서 두 핵심 고차 타입인 행위(Behavior)와 이벤트(Event)를 기반으로 반응적 시스템을 선언적으로 프로그래밍 한다. 이 논문은 다양한 제약사항을 가진 임비디드 시스템에 FRP를 이용하기 위해 실시간 함수형 반응적 프로그래밍(RT-FRP: Real-time Functional Reactive Programming) 변환기를 설계하고 구현한다. RT-FRP 변환기는 RT-FRP 언어의 기능적 의미론을 기반으로 RT-FRP 프로그램에서 C 프로그램을 생성한다. RT-FRP 변환기의 효과적인 변환을 입증하기 위해, 변환기에서 생성된 테스트 프로그램을 실제 임베디드 시스템, 레고 마인드스톰(LEGO Mindstorm)에 탑재하고 수행하였다. 실험 결과, RT-FRP를 이용할 경우 목적파일의 크기가 조금 증가하였으나 명령형 언어를 이용한 프로그램 보다 간결하게 반응적 시스템 소프트웨어를 프로그래밍 할 수 있었다. FRP(Functional Reactive Programming) is a kind of embedded language in Haskell, it declaratively program reactive system based on two essential high-order types named behavior and events. This Paper design and implementation RT-FRP(Real-time Functional Reactive Programming) translator for using FRP in embedded systems with many constraints. The RT-FRP translator generates a C Program from an RT-FRP program according to the operational semantics of the RT-FRP language. To show the effectiveness of the RT-FRP translator, we loaded and executed the test program generated by the translator onto a real embedded system, LEGO Mindstorm. According to the experimental result, the reactive system software can be programmed more concisely using RT-FRP than using an imperative counter part although the size of the binary code is rather increased.

분산 환경에서 CFD 분석 프로그램 수행을 위한 그리드 시스템 META 설계 및 구현

강경우,우균,Kang, Kyung-Woo,Woo, Gyun 한국정보처리학회 2006 정보처리학회논문지 A Vol.13 No.6

본 논문에서는 분산 환경 상에서 CFD(Computational Fluid Dynamics) 분석 프로그램을 편리하게 수행할 수 있도록 하는 그리드 시스템 META(Metacomputing Environment using Test-un of Application)의 설계 및 구현에 관하여 기술한다. 그리드 시스템 META는 CFD 프로그램 개발자들이 네트워크에 분산된 계산 자원들을 단일 시스템처럼 사용할 수 있도록 한다. 그리드 컴퓨팅과 관련하여 연구주제로는 고장허용, 자원 선택, 사용자 인터페이스 설계 등이 있다. 본 논문에서는 MPI(Message Passing Interface)로 작성된 SPMD(Single Program, Multiple Data) 구조의 병렬프로그램을 실행시키기 위한 자동 자원 선택방법을 활용하였다. 본 논문에서 제안한 자원 관리기법은 네트워크상의 전송지연 시간과 시험수행을 통해 얻어진 핵심루프의 경과시간을 이용한다. 전송지연시간은 병렬 프로그램이 복수의 시스템에 분산되어 수행될 때 수행 성능에 큰 영향을 주는 요인이다. CFD 프로그램들의 공통적인 특성 때문에 핵심루프 경과시간은 전체 수행시간을 예측할 수 있는 지표가 된다. 핵심루프는 CFD 프로그램의 전체 수행시간 중 90% 이상을 차지한다. This paper describes the design and implementation of a grid system META (Metacomputing Environment using Test-run of Application) which facilitates the execution of a CFD (Computational Fluid Dynamics) analysis program on distributed environment. The grid system META allows the CFD program developers can access the computing resources distributed over the network just like one computer system. The research issues involved in the grid computing include fault-tolerance, computing resource selection, and user-interface design. In this paper, we exploits an automatic resource selection scheme for executing the parallel SPMD (Single Program Multiple Data) application written in MPI (Message Passing Interface). The proposed resource selection scheme is informed from the network latency time and the elapsed time of the kernel loop attained from test-run. The network latency time highly influences the executional performance when a parallel program is distributed and executed over several systems. The elapsed time of the kernel loop can be used as an estimator of the whole execution time of the CFD Program due to a common characteristic of CFD programs. The kernel loop consumes over 90% of the whole execution time of a CFD program.

굼벨 분포 모델을 이용한 표절 프로그램 자동 탐색 및 추적

지정훈,우균,조환규,Ji, Jeong-Hoon,Woo, Gyun,Cho, Hwan-Gue 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.6

소프트웨어의 지적 재산권 보호 및 인증에 대한 관심과 중요성이 커지면서 소프트웨어에 대한 표절 탐색 및 보호, 판단에 대한 연구가 활발 하게 진행되고 있다. 지금까지 표절에 대한 연구는 주로 속성 계산, 토큰 패턴, 프로그램 파스트리, 유사도 측정 알고리즘 등을 이용해 두 프로 그램을 비교하는데 초점을 두었다. 이와 더불어, 표절과 협동(collaboration)을 구분하는 것은 표절연구에서 매우 중요하다. 본 논문에서는 극단 치 분포 확률 모델을 이용한 소스코드 클러스터링을 위한 알고리즘을 제안한다. 본 논문에서는 먼저 두 프로그램 먼저 두 프로그램 $P_a$와 $P_b$ 의 유사도를 측정하는 비대칭거리측정함수 pdist($P_a$, $P_b$)를 제안하고, 모든 소스코드 쌍에 대해 pdist($P_a$, $P_b$)를 통해 측정된 유사도를 간선무게로 하는 표절방 향그래프(PDG)를 생성한다. 그리고 본 논문에서는 표절방향그래프를 굼벨거리그래프(GDG)로 변환한다. pdist($P_a$, $P_b$) 점수 분포는 극단치 확률 분포로 잘 알려진 굼벨분포(Gumbel distribution)와 매우 유사하다. 또한, 본 논문에서는 의사표절(pseudo- plagiarism)을 새롭게 정의한다. 의사표절은 프로그램의 강한 기능적 제약사항으로 인해 발생하는 가상 표절의 한 종류이다. 본 논문에서는 ICPC(International Collegiate Programming Contest)와 KOI(Korean Olympiad for Informatics) 대회에 제출된 18개 프로그램 그룹의 700개 이상의 소스코드에 대해 실험을 진행하였다. 실험결과 프로그램 그룹에 포함된 표절 프로그램들을 찾았으며, 소스코드 클러스터링 알고리즘은 의사표절과 실제표절 프로그램 그룹을 효과적으로 구분하였다. Studies on software plagiarism detection, prevention and judgement have become widespread due to the growing of interest and importance for the protection and authentication of software intellectual property. Many previous studies focused on comparing all pairs of submitted codes by using attribute counting, token pattern, program parse tree, and similarity measuring algorithm. It is important to provide a clear-cut model for distinguishing plagiarism and collaboration. This paper proposes a source code clustering algorithm using a probability model on extreme value distribution. First, we propose an asymmetric distance measure pdist($P_a$, $P_b$) to measure the similarity of $P_a$ and $P_b$ Then, we construct the Plagiarism Direction Graph (PDG) for a given program set using pdist($P_a$, $P_b$) as edge weights. And, we transform the PDG into a Gumbel Distance Graph (GDG) model, since we found that the pdist($P_a$, $P_b$) score distribution is similar to a well-known Gumbel distribution. Second, we newly define pseudo-plagiarism which is a sort of virtual plagiarism forced by a very strong functional requirement in the specification. We conducted experiments with 18 groups of programs (more than 700 source codes) collected from the ICPC (International Collegiate Programming Contest) and KOI (Korean Olympiad for Informatics) programming contests. The experiments showed that most plagiarized codes could be detected with high sensitivity and that our algorithm successfully separated real plagiarism from pseudo plagiarism.