기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
피라미드의 3-차원 메쉬로의 신장율 개선 임베딩
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 피라미드의 3-차원 메쉬로의 신장율 개선 임베딩
저자명
장정환,Chang. Jung-Hwan
간행물명
정보처리학회논문지. The KIPS transactions. Part A. Part A
권/호정보
2003년|6호|pp.627-634 (8 pages)
발행정보
한국정보처리학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

본 논문에서는 주어진 손님 그래프 모델의 정점들과 간선들을 신장율, 혼잡율 등의 성능 파라미터들을 보다 우수하게 유지하면서 주인 그래프의 대응되는 정점들 및 경로들오 매핑시키는 "그래프 임베딩 문제"라고 불리는 그래프이론 문제를 다른다. 먼저 높이가 N인 파라미트 모델을 높이가 $(4^{(N+1)/3}+2)/3$ 이고 2-차원 정방현 메쉬의 한 변의 길이가 $2^{(2N-1)/3}$인 3-차원 메쉬 구조의 대규모 병렬처리시스템으로 임베딩 할 수 잇는 새로운 매핑함수를 제안하고, 해당 임베딩 하에서 인접된 두 정점들 상호간 통신에 필요한 단계의 수를 반영하는 신장율의 관점에서 성능을 분석한다. 본 임베딩의 신장율이 $2{cdot}4^{(N-2)/3}+4)/3$ 임을 증명한다. 이러한 결과는 동일한 조건 하에서 기존의 결과인 $4^{N+183}+2)/3$ 보다 우수한 것이다.다 우수한 것이다.

기타언어초록

In this paper, we consider a graph-theoretic problem,, the so-called "graph embedding problem" that maps the vertices and edges of the given guest graph model into the corresponding vertices and paths of the host graph under the condition of maintaining better performance parameters such as dilation, congestion, and expansion. We firstly propose a new mapping function which can embed the pyramid model with height N into the 3-dimensional mesh massively parallel processor system with the height $(4^{(N+1)/3}+2)/3$ and the regular 2-dimensional mesh of one side $2^{(2N-1)/3}$, and analyze the performance of the embedding in terms of the dilation parameter that reflects the number of communication steps between two adjacent vertices under the embedding. We prove that the dilation of the embedding is $2{cdot}4^{(N-2)/3}+4)/3$. This is superior to the previous result of $4^{N+183}+2)/3$ under the same condition.condition.