지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 1998.6
- 수록면
- 582 - 592 (11page)
이용수
초록· 키워드
오류제보하기
단일층 배선 문제는 소자(module)의 경계상에 단자들의 집합 {a₁,a₂,...,a_n}과 {b₁,b₂,...,b_n} 이 주어질 때, a₁와b₁(1≤i≤n)를 연결하는 n개의 네트들이 소자내에 있으며 서로 교차하지 않도록 배선하는 것이다. 이 문제에 대한 지금 까지의 가장 좋은 연구 결과는 COMMON CRCW PRAM 모델에서 O(log n/log log n)시간과 O(n) 연산, 그리고 EREW PRAM 모델에서 O(log n) 시간과 O(n) 연산을 사용하는 최적 병렬 알고리즘이다.
본 논문에서는 직사각형내에서 배선할 입력 네트의 개수가 n=p^(1+ε)(ε는 양의 상수)이고 단자의 범위가 0에서 O(n) 사이의 정수인 경우에, 대표자 네트를 배선하는 문제를 p개의 프로세서를 가지는 파이프라인 하이퍼큐브에서 O(n/p) 시간에 최적으로 해결하였다. 이는 기존 연구에 사용된 PRAM 모델보다 하드웨어적으로 구현이 더 쉬운 모델에서 같은 연산수 O(n)을 사용한 연구 결과이므로 의미가 있다고 생각된다.
본 논문에서는 직사각형내에서 배선할 입력 네트의 개수가 n=p^(1+ε)(ε는 양의 상수)이고 단자의 범위가 0에서 O(n) 사이의 정수인 경우에, 대표자 네트를 배선하는 문제를 p개의 프로세서를 가지는 파이프라인 하이퍼큐브에서 O(n/p) 시간에 최적으로 해결하였다. 이는 기존 연구에 사용된 PRAM 모델보다 하드웨어적으로 구현이 더 쉬운 모델에서 같은 연산수 O(n)을 사용한 연구 결과이므로 의미가 있다고 생각된다.
목차
요약
Abstract
1. 서론
2. 계산 모델 및 기본 문제
3. 직사각형내에서의 단일층 배선
4. 대표자 네트 찾기와 그룹화
5. 대표자 네트의 배선
6. 결론
참고문헌
저자소개
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
EREW PRAM 에서 문자열 정렬을 위한 최적 연산 병렬 알고리즘
정보과학회논문지(A)
1996 .06
-
EREW PRAM 모델에서의 단일층 배선에 관한 최적 병렬 알고리즘
(구)정보과학회논문지
1994 .12
-
파이프라인 하이퍼큐브상에서 단함수 최소 분리 문제를 해결하는 최적 병렬 알고리즘
정보과학회논문지(A)
1997 .06
-
이진트리의 최소컷 선형배열에 관한 병렬 알고리즘
정보과학회논문지(A)
1996 .01
-
트리에서 경로 합을 구하는 병렬 알고리즘
(구)정보과학회논문지
1994 .01
-
병렬 초근원성 테스트를 위한 최적 O(log log n) 시간 알고리즘
(구)정보과학회논문지
1994 .08
-
직사각형내의 단일층 배선을 위한 최적 병렬 알고리즘
(구)정보과학회논문지
1993 .07
-
최소신장트리를 구하는 효율적인 병렬 알고리즘
정보과학회논문지(A)
1996 .08
-
구간 그래프와 순열 그래프의 최대 가중치 독립 집합을 찾는 병렬 알고리즘
정보과학회논문지(A)
1996 .03
-
최소신장트리 문제에 대한 효율적인 병렬 알고리즘
한국정보과학회 학술발표논문집
1995 .10
-
매칭 문제를 위한 효율적인 랜덤 병렬 알고리즘
정보과학회논문지(A)
1999 .10
-
구간 그래프와 순열 그래프의 최대 가중치 독립 집합을 찾는 병렬 알고리즘
한국정보과학회 학술발표논문집
1995 .04
-
EREW PRAM 상에서 단함수 최소 분리 문제를 위한 효율적인 병렬 알고리즘
한국정보과학회 학술발표논문집
1996 .10
-
사각형내의 단일층 라우팅을 위한 최적 병렬 알고리즘
한국정보과학회 학술발표논문집
1992 .04
-
파이프라인드 하이퍼큐브(Pipelined hypercube) 모델상에서의 효율적인 정수 정렬 알고리즘
한국정보과학회 학술발표논문집
1991 .04
-
PRAM 기술 전망
[ETRI] 전자통신동향분석
2005 .12
-
A Buffer Cache Replacement Algorithm for Considering both Hybrid Main Memory and Storage
Journal of KIISE
2015 .08
-
K - 비대응 문제를 위한 선형 이하의 평균 시간 알고리즘
(구)정보과학회논문지
1995 .05
-
A Comparative Study of PRAM-based Join Algorithms
Journal of KIISE
2015 .03
-
파이프라인 하이퍼큐브에서의 효율적인 정수 정렬 알고리즘
(구)정보과학회논문지
1991 .12
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017732444