정보과학회 논문지 B : 소프트웨어 및 응용
Current Result Document : 1 / 5
| 한글제목(Korean Title) |
문맥자유 문법을 위한 병렬 파싱 알고리즘의 설계 및 성능 분석 |
| 영문제목(English Title) |
Design and Performance Analysis of a Parallel Algorithm for Context-Free Grammars |
| 저자(Author) |
나동렬
이진호
김종현
Dongyul Ra
Jinho Lee
Jonghyun Kim
|
| 원문수록처(Citation) |
VOL 23 NO. 09 PP. 0972 ~ 0981 (1996. 09) |
한글내용
(Korean Abstract) |
본 논문에서는 일반적인 문맥 자유 언어(Context-Free Language; CFL)를 인식하고 파싱하기 위한 병렬 알고리즘을 제안한다. 이 알고리즘은 하이퍼큐브와 같은 소결합 다중프로세서 시스템(loosely-coupled multiprocessor system)에 적합하도록 설계되었다. 이를 위한 시스템 구조는 간단한 링(ring) 구조이면 되며, n을 입력스트링의 길이라 할때 프로세서의 수 p는 n이하의 임의의 수이면 된다( 즉, 1≤p≤n ). 분석결과에 따르면 제안한 병렬 알고리즘의 시간 복잡도(time complexity)는 최악의 경우에 O(n³/p) 인 것으로 나타났다. 이 알고리즘은 Earley의 알고리즘에 기반을 두고 있기 때문에 임의의 문맥 자유 문법(Context-Free Grammar; CFG)에 대하여 적용될 수 있다. 이 알고리즘은 간단한 작업 배치 방법을 이용하였음에도 높은 성능 향상을 얻을 수 있었다.
|
영문내용
(English Abstract) |
In this paper, a parallel algorithm is given for recognizing and parsing arbitrary context-free language. The algorithm operates on multiprocessor systems with loosely-coupled architectures including hypercubes. The requirement on the architecture is simple : The processors need to form just a one-way ring. The requirement on p, the number of processors used, is also flexible: any p satisfying 1≤p≤n (where n is the length of the input string). The analysis show that the algorithm operates in O(n³/p) time in the worst case. This is the optimal performance one can get with the given architecture. Our parallel algorithm is based on Earley's algorithm and thus it can be used for arbitrary context-free grammars. High performance was achieved with a simple job allocation strategy.
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
