PLA와 SLA에 適用可能한 Folding Algorithm의 硏究

국문 초록 (Abstract)

本 論文에서는 PLA(Programmable Logic Array)의 Folding 알고리즘과 SLA(Storage Logic Arrary)의 特性을 調査하여 SLA의 Folding이 PLA Folding의 制限的인 경우임을 몇가지 制約條件을 提示하여 보였다. 우선 PLA, SLA를 personality Matrix(PM)으로 바꾸어 몇 가지 簡略化(빈 행열과 동일 행열제거)와 變換作業(對角行列 형태로 변환, 列이 많은 행열형태로 변환)을 通하여 PM을 간단히 한후 Generate and text, Most favorable Branch and Bound 方式으로 Folding 한다.
Generation 段階에서 Folding 가능한 例 사이의 교차도를 포함하는 Weighted Independency Graph(WIG)를 定義하여 Edmond의 Weighted Matching 알고리즘을 적용하여 Folding할 例의 쌍의집합 PM'을 O(n³()⁴)속도로 구한다. 테스팅 단계에서는 2가지 Determinent를 이용하여 PM'의 Folding 가능여부를 판단하고 가능할 경우에만 獨立 行區間에 대해 再配置하여 Folding을 完成하고 不可能할 경우에는 Generation에서 새로운 PM'을 구해 테스팅을 실시한다. 이로써 Folding 시간을 Polynomial time으로 할 수 있게 하였다.

목차 (Table of Contents)

• Ⅰ. 序 論
• Ⅱ. SLA와 PLA Folding 알고리즘
• 1. SLA
• 2. PLA Folding 알고리즘
• 3. PLA Folding SLA Folding
• Ⅲ. PLA/SLA Folding 알고리즘
• 1. 준비 단계
• 2. Generation 단계
• 3. Testing 단계
• Ⅳ. 例
• Ⅴ. 分析 및 結論
• 參考文獻
• 要 約