지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 1997.6
- 수록면
- 542 - 552 (11page)
이용수
초록· 키워드
오류제보하기
단함수 최소 분리 문제는 n개의 원소를 가진 집합 S와 S의 초기 분리 B={B₁, B₂, ... B_ｋ}와 S상에서의 함수 f가 주어질 때, B와 f에 일치하는 S의 최소 분리 Q={Q₁, Q₂, ... Q_m}를 찾는 문제이다. 이 문제를 해결하는 지금까지의 가장 좋은 결과는 Arbitrary CRCW PRAM에서 O(logn) 시간과 O(nloglogn) 연산을 사용 하는 병렬 알고리즘과, Priority CRCW PRAM상에서 O(logn) 시간과 O(n) 연산을 사용하는 최적 임의(randomized) 병렬 알고리즘인데, 이 두 알고리즘 모두 O(n^(1+λ)) (0< λ <l)만큼의 기억 용량을 사용한다.
본 논문에서는 입력 원소의 개수가 n=p^(1+ε)(ε는 양의 상수) 개인 주이진 문제를 p개의 프로세서를 가지는 파이프라인 하이퍼큐브에서 O(n/p) 시간과 O(n) 기억장소만 사용하는 최적 병렬 알고리즘을 제시하는데, 이는 PRAM 모델보다 하드웨어의 구현이 더 쉬운 모델에서 같은 연산수와 더 적은 기억 용량만을 사용하는 알고리즘이므로 큰 의미가 있다고 생각된다.
본 논문에서는 입력 원소의 개수가 n=p^(1+ε)(ε는 양의 상수) 개인 주이진 문제를 p개의 프로세서를 가지는 파이프라인 하이퍼큐브에서 O(n/p) 시간과 O(n) 기억장소만 사용하는 최적 병렬 알고리즘을 제시하는데, 이는 PRAM 모델보다 하드웨어의 구현이 더 쉬운 모델에서 같은 연산수와 더 적은 기억 용량만을 사용하는 알고리즘이므로 큰 의미가 있다고 생각된다.
목차
요약
Abstract
1. 서론
2. 모델 및 기본 문제
3. 단함수 최소 분리 문제
4. 사이클 노드의 최종 분리 값 구하기
5. 트리 노드의 최종 분리 값 구하기
6. 결론
참고문헌
저자소개
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
파이프라인드 하이퍼큐브(Pipelined hypercube) 모델상에서의 효율적인 정수 정렬 알고리즘
한국정보과학회 학술발표논문집
1991 .04
-
파이프라인 하이퍼큐브에서의 효율적인 정수 정렬 알고리즘
(구)정보과학회논문지
1991 .12
-
파이프라인 하이퍼큐브에서 단일층 배선을 위한 최적 병렬 알고리즘
정보과학회논문지(A)
1998 .06
-
토폴로지 특성에 기초를 둔 효율적인 하이퍼큐브 인지 알고리즘
(구)정보과학회논문지
1994 .09
-
하이퍼큐브를 위한 최적의 프로세서 할당 알고리듬 ( Optimal Processor Allocation Algorithm in a Hypercube )
대한전자공학회 학술대회
1992 .11
-
병렬 파이프라인 프로세서 아키텍처의 설계 ( Design of a Parallel Pipelined Processor Architecture )
전자공학회논문지-B
1995 .03
-
2*n 행렬하이퍼큐브 : 하이퍼큐브 에지를 1/2로 개선한 상호연결망
한국통신학회 학술대회 및 강연회
2008 .04
-
하이퍼큐브 시스템 상에서의 병렬 프로그램 알고리듬
대한전자공학회 학술대회
1992 .06
-
하이퍼큐브 시스템 상에서의 병렬 프로그램 알고리듬 ( A Concurrent Program Algorithm in Hypercube Systems )
대한전자공학회 학술대회
1992 .07
-
공유기억 다중프로세서의 파이프라인 버스 ( A Pipelined Bus for the Shared Memory Multiprocessor )
대한전자공학회 학술대회
1991 .11
-
하이퍼큐브 멀티프로세서 시스템을 위한 부하분산 알고리즘
(구)정보과학회논문지
1989 .07
-
행렬 하이퍼큐브에 대한 방송 알고리즘
대한전자공학회 학술대회
1998 .11
-
행렬 하이퍼큐브에 대한 방송 알고리즘 ( A Broadcasting Algorithm in Matrix Hypercubes )
대한전자공학회 학술대회
1998 .11
-
하이퍼큐브 시스템에서 데이타 비대칭성을 고려한 향상된 병렬 결합 알고리즘
정보과학회논문지 : 시스템 및 이론
2003 .04
-
코하이퍼큐브 : 원형군 그래프와 하이퍼큐브의 연산에 의한 병렬 컴퓨터의 위상
(구)정보과학회논문지
1994 .08
-
파이프라인 방식의 버스를 위한 비동기식 주 기억장치의 설계 및 구현 ( Design and Implementation of Asynchronous Memory for Pipelined Bus )
전자공학회논문지-B
1994 .11
-
일반화된 회선교환 하이퍼큐브 구조의 재배열성 및 고장허용 능력
(구)정보과학회논문지
1994 .08
-
파이프라인 시스템의 최적화를 위한 설계 변환 ( Design Transformation for the Optimization of Pipelined Systems )
전자공학회논문지-C
1999 .03
-
Note on the Partial Sum Problem Mapping into a Hypercube
대한전기학회 학술대회 논문집
1990 .11
-
Half 하이퍼큐브(Hypercube)의 효율적인 라우팅
대한전자공학회 학술대회
2013 .07
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017726888