지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 1988.10
- 수록면
- 354 - 368 (15page)
이용수
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
본 논문에서는 한 부류의 NP-complete 문제에 대하여 완전 이진트리 배열을 사용한 systolic 시스템에 기초한 병렬 알고리즘을 연구한다. 모든 결과는 0/1 knapsack 문제에 대한 것이나 0/1 정수 프로그래밍(integer programming) 문제, 부분집합의 합(sum of subset) 문제, 집합 커버링(set covering) 문제 등과 같은 유형의 NP-complete 문제들을 유사한 방법으로 해결할 수 있다. 우리가 제시하는 병렬 알고리즘을 구성하는데 있어서 우선, n개의 수들의 집합의 모든 부분집합의 합을 계산하고 특정한 조건을 만족하는 합을 구하는 자료구조를 효율적으로 수행할 수 있는 완전 이진트리 구조를 갖는 systolic 트리 배열을 구현하고, 이 systolic 배열을 사용하여 0/1 knapsack 문제를 O(n) 시간 내에 O(2ⁿ)의 area complexity로 해결할 수 있음을 보이고, 또한 트리 배열의 area complexity를 1/2로 줄일 수 있음을 보였다. 트리 배열에서 계산된 부분합들로 heap을 구성하여 기존의 각각 O(2 ⁿ / ²), O(2 ⁿ / ⁴) area complexity를 갖고 O(2 ⁿ / ²) time complexity를 갖는 two-list 알고리즘과 four-table 알고리즘을 systolic 시스템에 구현하였다. 기존의 결과와는 달리 우리의 two-list 알고리즘의 systolic 시스템 구현은 time complexity에서 logarithmic factor를 무시하지 않은 결과를 얻었고, 또한 모든 구현에서 해와 관련된 부분집합의 0/1 해벡터를 complexity의 추가 부담 없이 쉽게 구할 수 있다.
목차
요약
ABSTRACT
1. 서론
2. n레벨 트리 구조를 이용한 알고리즘
3. n-1 레벨 트리 구조를 이용한 알고리즘
4. Two-list 알고리즘
5. Four-table 알고리즘
6. 결론
참고문헌
저자소개
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
한 부류의 NP - complete 문제에 대한 Systolic 트리 알고리즘
한국정보과학회 학술발표논문집
1987 .10
-
원전작업에서의 복잡도 기여요인 분석에 관한 연구
대한인간공학회 학술대회논문집
2002 .11
-
단어인식 알고리즘의 병렬 처리를 위한 systolic 구조에 관한 연구 ( A Study on the Systolic Architecture for the Parallel Processing of Word Recognition Algorithms )
대한전자공학회 학술대회
1987 .11
-
R-S 복호기의 Systolic 설계에 관한 연구 ( A Study on the Systolic Architecture of R-S Decoder )
대한전자공학회 학술대회
1988 .07
-
R-S 복호기의 Systolic 설계에 관한 연구
대한전기학회 학술대회 논문집
1988 .07
-
The Relationship of Complexity and Order in Determining Aesthetic Preference in Architectural Form
ARCHITECTURAL RESEARCH
2011 .12
-
COMPUTER AIDED SYSTOLIC ARCHITECTURE DESIGN
JTC-CSCC : Joint Technical Conference on Circuits Systems, Computers and Communications
1989 .01
-
Systolic Architecture in Signal Processing
대한전자공학회 단기강좌
1988 .01
-
고속 신호 처리용 Systolic Array 설계 ( A High Speed Signal Processing Systolic Array Design )
한국통신학회 학술대회논문집
1985 .01
-
Systolic Array 구조를 갖는 움직임 추정기 설계 ( Design of a Motion Estimator with Systolic Array Structures )
전자공학회논문지-C
1997 .10
-
Systolic Array 구조를 갖는 Processing Element 설계 ( The Design of Processing Element with Systolic Array Structures )
대한전자공학회 학술대회
1996 .07
-
A Qualitative Method to Estimate HSI Display Complexity
Nuclear Engineering and Technology
2013 .01
-
Design of Fixed-Size Systolic Arrays
Journal of Electrical Engineering and information Science
1999 .06
-
Implementation of systolic array for 2-D IIR digital filters
한국음향학회 학술발표대회
1992 .01
-
A Study on Calculation with Extended Systolic Array
ITC-CSCC :International Technical Conference on Circuits Systems, Computers and Communications
2003 .07
-
Assessing Urban Complexity
International journal of sustainable building technology and urban development
2010 .01
-
An Analysis of Product Complexity Index : Focus on the relation between product architecture and structural complexity
대한인간공학회 학술대회논문집
2014 .05
-
로봇 운동솜씨의 작업 복잡도
로봇학회 논문지
2012 .09
-
Identification and Organization of Task Complexity Factors Based on a Model Combining Task Design Aspects and Complexity Dimensions
대한인간공학회지
2013 .02
-
A PSEUDO PARALLEL ARCHITECTURE FOR SYSTOLIC ALGORITHMS
ICVC : International Conference on VLSI and CAD
1989 .01
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017775821