LR 파서를 위한 효율적인 점진적 파싱

안희학(Ahn Heui Hak) 한국정보처리학회 1998 정보처리학회논문지 Vol.5 No.6

In this paper, we review the conventional incremental parsing algorithms which are too expensive in time and memory space to be of practical use, and we propose an incremental LR parsing algorithm which is more efficient than the previous ones. We apply an extended LR parsing table including grammar symbols to our incremental LR parsing algorithm. We show that the parsing steps and memory spaces in our incremental LR parsing algorithm are reduced in several sentences. Our algorithm is more effective in the case of complex and large grammars.

다중 SNS 채널을 위한 RELAY 모듈의 구현 및 실험

안희학(Heui-Hak Ahn),이대식(Dae-Sik Lee) 한국정보전자통신기술학회 2018 한국정보전자통신기술학회논문지 Vol.11 No.4

본 논문에서는 외부 스트리밍 서버의 출력 채널을 포함한 복수의 출력 채널을 통해 다중 SNS 채널 자동 스트리밍 하는 방법을 제안한다. 다중 SNS 채널 자동 스트리밍 서버는 2개 이상의 출력 채널을 설정하는 RELAY module로 동영상 콘텐츠의 송신을 제어하는 출력 관리 모듈을 포함한다. 본 논문에서는 다중 SNS 채널 자동 스트리밍에서 RELAY module을 사용하여 HD와 FHD 동영상으로 구분하여 실험하였다. HD 동영상의 RELAY module을 사용하는 RELAY 스트림에서 publisher client는 1 채널, player client는 1 채널, 그리고 RELAY module 1일 때 CPU의 점유율은 0.6%이고, heap memory의 점유율은 0.3%인 20Mbyte이다. publisher client는 183 채널, player client는 183 채널, RELAY module 183일 때 CPU의 점유율은 99.9%이고, heap memory의 점유율은 45.8%인 3.7Gbyte이다. 따라서 동영상이 송출되는 출력 채널을 외부 스트리밍 서버의 출력 채널을 확장함으로 스트리밍 서버의 규모에 제한이 되지 않는다. 그리고 외부 스트리밍서버의 출력 채널을 동영상이 송출되는 출력 채널로 할당하는 과정이 용이하게 이루어져 다수의 동영상 송출 시에도 효율적인 출력 채널 관리가 가능하다. In this paper, we propose a procedure to multiple SNS channels automatic streaming through multiple output channels including the output channel of an external streaming server. The multiple SNS channels automatic streaming server includes an output management module for controlling the transmission of video contents to RELAY module that establish two or more output channels. In this paper, we experimented by separate with HD and FHD video using RELAY module in multiple SNS channel automatic streaming. In stream modules using RELAY module of HD video, when the publisher client and the player client and the RELAY module are 1 channel, the occupancy rate of CPU is 0.6% and the occupancy rate of heap memory is 0.3%(20 Mbyte). When the publisher client and the player client and the RELAY module are 183 channels, the occupancy rate of CPU is 99.9% and the occupancy rate of heap memory is 45.8%(3.7Gbyte). Therefore, the paper is not limited to the size of the streaming server by extending the output channel from which the video is transmitted to the output channel of the external streaming server. And a process of allocating an output channel of an external streaming server to an output channel through which an video is transmitted can be easily performed, so that an efficient output channel management can be performed even when a plurality of videos are transmitted.

추론적 부분 중복 제거의 최적화 예외 영역 문제 해결 알고리즘

신현덕,안희학,Shin, Hyun-Deok,Ahn, Heui-Hak 한국정보처리학회 2006 정보처리학회논문지 A Vol.13 No.6

본 논문에서는 Knoop 등이 2004년에 제안한 추론적 부분 중복 제거 알고리즘을 개선한다. 본 연구에서는 기존 추론적 부분 중복 제거에서 최적화가 적용되지 않는 영역이 발생될 수 있는 문제를 제기하고 이 문제에 대한 해법을 제안한다. 개선된 추론적 부분 중복 제거 알고리즘은 컴파일러의 프로필링 기법을 통해 얻어진 실행 빈도에 대한 정보를 통해 실행 속도 최적화를 수행하며 메모리 최적화도 수행한다. This paper improves the algorithms for Speculative Partial Redundancy Elimination(SPRE) proposed by Knoop et al. This research brings up an issue concerning a field to which SPRE cannot be applied, and suggests a solution to the problem. The Improved SPRE algorithm performs the execution speed optimization based on the information on the execution frequency from profiling and the memory space optimization.

점진적 속성문법을 위한 효과적인 최적화 알고리즘에 관한 연구

장재춘,안희학,Jang, Jae-Chun,Ahn, Heui-Hak 한국정보처리학회 2001 정보처리학회논문지 A Vol.8 No.3

복잡한 언어 처리에 점진적 속성 문법을 적용하기 위해서는 최적화 알고리즘을 사용하는 것이 효과적이다. 점진적 속성문법의 최적화 알고리즘에서는 새로운 입력 속성 트리가 기존 입력 속성 트리와 정확히 비교되어서 새로운 속성 트리를 구성할 대 기존 속성 트리의 어떤 서브트리를 사용해야 하는가를 결정한다. 본 논문에서는 Carle과 Pollock에 의해 제안된 알고리즘을 분석하여 효과적인 최적화 알고리즘으로 재구성하고, 새로은 속성 트리 d'copy의 생성 과정과, 속성트리 d'copy의 새로운 최적화 알고리즘을 추가하였다. 이 논문에서 제안한 매칭 알고리즘의 성능평가를 통하여 기존의 알고리즘 보다 제안한 최적화 알고리즘의 실행 시간을 약 19.5% 향상 시킬 수 있었다. The effective way to apply incremental attribute grammar to a complex language process is the use of optimized algorithm. In optimized algorithm for incremental attribute grammar, the new input attribute tree should be exactly compared with the previous input attribute tree, in order to determine which subtrees from the old should be used in constructing the new one. In this paper the new optimized algorithm was reconstructed by analyzing the algorithm suggested by Carle and Pollock, and a generation process of new attribute tree d’copy was added. Through the performance evaluation for the suggested matching algorithm, the run time is approximately improved by 19.5%, compared to the result of existing algorithm.

불필요한 코드모션 억제를 위한 배정문 모션 알고리즘

신현덕,안희학,Shin, Hyun-Deok,Ahn, Heui-Hak 한국정보처리학회 2001 정보처리학회논문지 A Vol.8 No.1

본 논문에서는 코드 최적화를 위하여 계산적으로나 수명적으로 제한이 없는 배정문 모션 알고리즘을 제안한다. 이 알고리즘은 지나친 레지스터의 사용을 막기 위하여 불필요한 코드 모션을 억제한다. 본 논문은 최종 최적화단계가 추가된 재정문 모션 알고리즘을 제안한다. 또한 기존 알고리즘의 술어의 의미가 명확하지 않은 것을 개선하였고 노드 단위 분석과 명령어 단위 분석을 혼용했기 때문에 발생하는 모호함도 개선하였다. 따라서 제안한 알고리즘은 불필요하게 중복된 수식이나 배정문의 수행을 피하게 함으로써, 프로그램의 불필요한 재계산이나 재실행을 하지 않게 하여 프로그램의 능률 및 실행시간을 향사시킨다. This paper presents the assignment motion algorithm unrestricted for code optimization computationally. So, this algorithm is suppressed the unnecessary code motion in order to avoid the superfluous register pressure, we propose the assignment motion algorithm added to the final optimization phase. This paper improves an ambiguous meaning of the predicated. For mixing the basic block level analysis with the instruction level analysis, an ambiguity occurred in knoop’s algorithm. Also, we eliminate an ambiguity of it. Our proposal algorithm improves the runtime efficiency of a program by avoiding the unnecessary recomputations and reexecutions of expressions and assignment statements.

Ad-hoc 네트워크상에 Hotspot Zone을 이용한 효율적인 데이터 집계 설계

김주용,안희학,이병관,Kim, Ju-Yung,Ahn, Heui-Hak,Lee, Byung-Kwan 한국산업정보학회 2012 한국산업정보학회논문지 Vol.17 No.7

애드혹 네트워크에서는 제한된 자원과 전력을 가지고 있기 때문에 에너지 효율적인 데이터 집계 연산이 필요하다. 현재 데이터 집계 연산에 대한 연구는 활발히 진행되고 있지만 기존의 연구에서는 노드의 밀집도를 고려하지 못하였다. 노드가 특정 영역에 밀집 되어 배치된다면 그 영역에 배치된 센서 노드들이 센싱 하는 정보는 그 연관성이 아주 강하다고 판단할 수 있다. 이는 중복된 데이터를 수집하는 효과와 같다고 볼 수 있으며, 이 정보를 전송하는데 소모되는 에너지는 낭비된다고 볼 수 있다. 제안하는 기법에서는 AMC알고리즘을 이용한 다중홉 클러스터링 환경에서 노드들이 밀집되어 있는 지역을 핫스팟 영역으로 지정하여 해당 지역에서 대표노드를 선정한다. 만약 데이터집계의뢰 메시지를 전송받으면, 주변의 노드를 대표하여 대표노드가 해당 환경 정보를 관리자에게 제공하여 중복되는 센싱 정보를 줄여 네트워크 수명을 증가시킬수 있도록 설계하였다. As the resources and power on Ad-hoc networks are limited, new data aggregation techniques are required for energy efficiency. The current research on data aggregation techniques is actively in progress, but existing studies don't consider the density of nodes. If nodes are densely placed in a particular area, the information which the sensor nodes placed on those areas detect can be judged as very strong association. But, the energy spent transmitting this information is a waste of energy. In this paper the densely-concentrated node area is designated as Hotspot_Zone in the multi-hop clustering environment using the AMC and a key node is selected in the area. If the request message of data aggregation is transmitted, the key node among the neighboring nodes sends its environmental information to a manager to avoid duplicate sensing information. Therefore, the life of networks can be prolonged due to this.

커넥티드카 인포테인먼트 시스템의 분석 및 설계

조병호,안희학,Cho, Byung-Ho,Ahn, Heui-Hak 한국인터넷방송통신학회 2017 한국인터넷방송통신학회 논문지 Vol.17 No.5

커넥티드카는 연결성이 주요 요소로서 항시 LTE나 5G 무선이동통신에 의한 인터넷 접속이 가능하여 인포테인먼트 기능 구현에 있어 새로운 개념의 스마트PC 하드웨어 및 서버의 음성인식 엔진을 이용한 디지털 가상비서의 소프트웨어 설계 방법을 활용할 수 있다. 본 논문에서는 음성인식 기술에 기반한 커넥티드카 인포테인먼트 시스템 구현을 위하여 스마트 오토PC의 하드웨어 및 GENIVI 플랫폼에서의 소프트웨어 구조와 필요한 기능 등을 제시한다. 또한 객체지향 분석 방법을 이용하여 사용자 요구사항 분석, 플로우차트 및 화면 설계를 보여줌으로 효과적인 커넥티드카 인포테인먼트 소프트웨어 분석 및 설계 방법을 제시하고자 한다. A connected car's major factor is connectivity and it can be applied for new concept smart PC hardware and software design method of digital virtual assistance using voice recognition engine at server when infotainment functions are implemented because internet connecting LTE or 5G wireless mobile communication is always is possible. In this paper, a hardware architecture of smart auto-PC and software architecture based on GENIVI platform, and necessary functions are proposed. Also an effective analysis and design method of connected car infotainment system will be presented by showing user requirement analysis using object-oriented method, flowchart and screen design.

경로 압축을 이용한 DJ 그래프의 지연 감축 알고리즘

심손권,안희학,Sim, Son-Kwon,Ahn, Heui-Hak 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.2

The effective and accurate data flow problem analysis uses the dominator tree and DJ graphs. The data flow problem solving is to safely reduce the flow graph to the dominator tree. The flow graph replaces a parse tree and used to accurately reduce either reducible or irreducible flow graph to the dominator tree. In this paper, in order to utilize Tarian's path compress algorithm, the Top node finding algorithm is suggested and the existing delay reduction algorithm is improved using Path compression. The delayed reduction a1gorithm using path compression actually compresses the pathway of the dominator tree by hoisting the node while reducing to delay the DJ graph. Realty, the suggested algorithm had hoisted nodes in 22% and had compressed path in 20%. The compressed dominator tree makes it possible to analyze the effective data flow analysis and brings the improved effect for the complexity of code optimization process with the node hoisting effect of code optimization process. 효과적이고 정확한 데이터 흐름 문제 분석은 흐름그래프와 지배자 트리 그리고 DJ 그래프를 사용한다. 데이터 흐름 문제 해결은 흐름 그래프를 안전하게 지배자 트리로 감축하는 것이다. 흐름 그래프는 파스 트리를 대신하고, DJ 그래프는 감축 가능하거나 감축이 불가능한 흐름 그래프를 지배자 트리로 정확하게 감축하는데 이용된다. 본 연구에서는 Tarjan의 경로 압축 알고리즘을 이용하기 위하여 Top 노드 찾기 알고리즘을 제시하고 기존의 지연감축 알고리즘을 경로압축을 이용하여 개선한다. 경로압축을 이용한 지연감축 알고리즘은 DJ 그래프를 지연 감축하면서 노드를 끌어올려 지배자 트리의 경로를 압축시킨다. 실제로 제안된 알고리즘은 22% 정도 노드들을 끌어올렸고, 20% 정도 경로를 압축시켰다. 압축된 지배자 트리는 효과적인 데이터 흐름 분석을 가능하게 하고, 코드 최적화 과정의 노드 끌어올리기 효과를 가져와 코드 최적화 과정의 복잡도를 개선하는 효과를 가져온다.

희소코드모션을 위한 효율적인 알고리즘

신현덕,유희종,안희학,Shin Hyun-Deok,Yu Heui-Jong,Ahn Heui-Hak 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.1

이 논문에서는 계산적으로나 수명적으로 코드를 최적화 하기 위해 절제된 코드 모션 알고리즘을 제안한다. 제한한 알고리즘은 BCM과 LCM 알고리즘을 확장한 SpCM 알고리즘이다. SpCM 알고리즘에서 BCM 알고리즘은 계산적으로 최적의 코드 모션을 수행하며, LCM 알고리즘은 레지스터 압박을 감소시킨다. 일반적으로, 코트 모션 알고리즘은 계산의 최적화와 레지스터 압박에 관련된 실행시간 최적화를 실행한다. 이 논문에서는 계산 비용과 레지스터 압박에 코드의 크기를 고려하는 부분을 추가하였다. 코드의 계산적 최적화와 수명적 최적화에 이어 코드의 크기를 고려하는 SpCM 알고리즘에 의해 코드 모션의 최적화 결과를 얻을 수 있다. 이 논문에서 제안한 알고리즘은 모든 불필요한 코드 모션을 억제시키기 때문에 계산적으로나 수명적으로 최적인 알고리즘이라 할 수 있다. This paper suggests that sparse code motion algorithm should be used to make the code optimal in the respect of computation and lifetime. This algorithm Is SpCM algorithm, which expand BCM and LCM algorithm. BCM algorithm carries out the optimal code motion computationally and LCM algorithm reduces the register pressure in SpCM algorithm. Generally, code motion algorithm accomplishes the run-time optimal connected with the optimum of computation and the register pressure. Computational cost and consideration of the code size in the register pressure are also added in the paper. The optimum of code motion could be obtained through SpCM algorithm, which considers the code size, in audition to computational optimal and lifetime optimal. The algorithm presented in this paper is the most optimal algorithm in the respect of computation and lifetime, as all the unnecessary code motions are restrained.

감축 불가능한 유향그래프로부터 지배자 트리를 구성하기 위한 효과적인 알고리즘

이대식,심손권,안희학,Lee, Dae-Sik,Sim, Son-Kweon,Ahn, Heui-Hak 한국정보처리학회 2000 정보처리논문지 Vol.7 No.8

지배자 트리란 유향그래프에서 지배관계를 트리로 표현한 것이다. 임의의 유향그래프로부터 지배자 트리를 구성하기 위한 효과적인 알고리즘을 제시한다. 감축 가능한 흐름그래프는 지배자 계산을 한 후 지배자 트리로 감축된다. 감축 불가능한 흐름그래프는 정보 테이블의 연결가지 정보를 이용하여 지배자 연결그래프로 구성된다. 지배자 연결그래프에서 지배자 트리로 감축하기 위하여 효과적인 순차감축 알고리즘과 지연감축 알고리즘을 제안한다. The dominator tree presents the dominance frontier from directed graph to the tree. we present the effective algorithm for constructing the dominator tree from arbitrarY directed graph. The reducible flow graph was reduced to dominator tree after dominator calculation. And the irreducible flow graph was constructed to dominator-join graph using join-edge information of information table. For reducing the dominator tree from dominator-join graph, we present the effective sequency reducible algorithm and delay reducible algorithm.