초록 ▼

VLSI 기술의 발달로 가격면으로나 기술적인 면으로 다수의 프로세서를 이용한 병렬 컴퓨터의 실현이 가능하게 되어, 그간 한개의 프로세서를 사용하여 문제 해결을 해왔던 순차 알고리즘에서 대신 다수의 프로세서를 사용하는 병렬 알고리즘에 대한 연구가 주목을 받게 되었다. 본 연구에서는 종래 2차원 systolic array를 사용하여 해결하였던 최대 공통부순서를 찾는 문제를 1차원 systolic array로서 해결하는 방법을 제시하였고, 또한 기존에 제시된 대부분의 systolic array는 오직 한 알고리즘만 수행 가능하였으나,

VLSI 기술의 발달로 가격면으로나 기술적인 면으로 다수의 프로세서를 이용한 병렬 컴퓨터의 실현이 가능하게 되어, 그간 한개의 프로세서를 사용하여 문제 해결을 해왔던 순차 알고리즘에서 대신 다수의 프로세서를 사용하는 병렬 알고리즘에 대한 연구가 주목을 받게 되었다. 본 연구에서는 종래 2차원 systolic array를 사용하여 해결하였던 최대 공통부순서를 찾는 문제를 1차원 systolic array로서 해결하는 방법을 제시하였고, 또한 기존에 제시된 대부분의 systolic array는 오직 한 알고리즘만 수행 가능하였으나, 본 연구에서는 여러개의 행렬계산 알고리즘을 수행할 수 있는 다양성 있는 systolic array를 설계하였다. 또한 특정한 상호 연결 구조를 갖는 병렬 컴퓨터 (Shuffle Exchange network or Tree-ring Interconnection)를 사용하여 자료(Dictionary machine, Relational Database Operations)를 병렬식으로 처리하는 방법을 연구하였고, 0/1-Knapsack 문제에 대한 시간효율적인 SIMD 알고리즘의 설계와 공간 복잡도(H)와 시간 복잡도(T) 사이에 HT?=0(2(sup)n)인 상관관계가 존재함을 보았다.

Abstract ▼

Due to the development of VLSI technology, it is possible economically and technically to implement a parallel computer using many processors. Now it gets a great deal of attention from many researchers to solve the problem by using several processors in psrallel instead of using a single processor.

Due to the development of VLSI technology, it is possible economically and technically to implement a parallel computer using many processors. Now it gets a great deal of attention from many researchers to solve the problem by using several processors in psrallel instead of using a single processor. In this study, we propose an one-dimensiona systolic array for finding a longest common subsequence which is shown to be done in 2-dimensional systolic array previously and we consider a design of versatile systolic array which can perform several matrix algorithms. Most of the previous results give systolic arrays each of which can perform exactly one algorithm. We consider the ways to process the data in parallel (Dictionary machines or Relational Database Operations) by using parallel computers with certain interconnection network (such as Shuffle Exchange network and Tree-Ring interconnection), and we find a time effjcient SIMD computer algorithm for 0/1-knapsack problem and a trade-off HT? = O(2(sup)(n)) between hardware complexity (H) and time complexity (T).

목차 Contents

• 목차...5
• 1. Shuffic Exchange Network를 이용한 사전머신...10
• 1.1. 서론...10
• 1.2. 사전머신의 정의...12
• 1.3. Shuffle-Exchange Network을 이용한 사전머신...15
• 1.4. 일괄 처리대 파이프 라인 처리의 성능 비교...29
• 1.5. 결론...30
• 2. O/1-knapsack 문제에 대한 시간 효율적인 병렬 알고리즘...31
• 2.1. 서론...31
• 2.2. SIMD 알고리즘...35
• 2.3. HT$^2$ = O($2^n$)...53
• 2.4. 결론...56
• 3. 행렬계산들을 위한 범용 시스톨릭 배열의 설계와 분할 기법에 관한 연구...57
• 3.1. 서론...57
• 3.2. 범용 시스톨릭 배열(GAS)의 설계 및 응용...61
• 3.3. GSA의 성능 평가...84
• 3.4. 결론...87
• 4. 관계 데이타베이스 연산의 병력 처리를 위한 트리-링 다중 컴퓨터의 설계...88
• 4.1. 서론...88
• 4.2. 트리-링 다중 컴퓨터...98
• 4.3. 응답 시간 비교 분석...112
• 4.4. 결론...136
• 5. 선형 시스톨릭 배열에서의 최대 공통 부순서 문제에 대한 해...138
• 5.1. 서론...138
• 5.2. 선형 시스톨릭 배열에 대한 순차 기계 특성화...141
• 5.3. 선형 시스톨릭 배열에서의 LCS 계산...149
• 5.4. 유한 상태 기계로 구성된 선형 시스톨릭 배열에서의 LCS 길이 계산...165
• 5.5. 유한 상태 기계로 구성된 선형 시스톨릭 배열에서의 제한된 LCS 문제에 대한 해...175
• 5.6. 결론...181
• 참고문헌...182