표제지
목차
Abstract 8
1. 서론 10
1.1. 연구배경 10
1.2. 연구내용 13
1.3. 논문구성 13
2. 관련 연구 15
2.1. 망 척도 15
2.1.1. 그래프적 특성 16
2.1.2. 경로 특성 17
2.1.3. 고장 허용도 18
2.1.4. 기타 20
2.2 상호연결망 21
2.2.1. 스타 그래프 21
2.2.2. 버블정렬 그래프 23
2.2.3. 전위 그래프 24
2.2.4. 팬케익 문제와 팬케익 그래프 25
3. Half Pancake Graph(HPG) 30
3.1. 정의 및 성질 30
3.1.1. HPG 정의 30
3.1.2. HPG의 재귀적 구성 33
3.1.3. 연결도 39
3.1.4. Half Pancake 과 팬케익의 관계 42
3.2. 라우팅 알고리즘과 지름 43
3.2.1. 간단한 라우팅 알고리즘 44
3.2.2. 지름 52
4. 결론 56
참고문헌 57
[표 1] HPG와 Pancake 그래프 분지수 비교 33
[표 2] 상호연결망의 망비용 비교 55
[그림 1.1] 병렬 컴퓨터 구조 11
[그림 2.1] 그래프로 표현된 상호연결망 15
[그림 2.2] 4차원 스타 그래프 22
[그림 2.3] 4차원 버블정렬 그래프 24
[그림 2.4] 4차원 전위 그래프 25
[그림 2.5] 4개의 팬케익이 담긴 접시의 정렬 26
[그림 2.6] 2~4차원 팬케익 그래프 예 28
[그림 3.1] 3차원 HPG HP₃ 31
[그림 3.2] 4차원 HPG HP₄ 31
[그림 3.3] HP6 그래프에서 노드 S=123456에 인접한 노드(이미지참조) 32
[그림 3.4] 5차원 HPG(HP5)의 ****5 클러스터 개요(이미지참조) 33
[그림 3.5] HP2k에서 노드 S에 인접한 노드(이미지참조) 35
[그림 3.6] HP2k+1에서 노드 S에 인접한 노드(이미지참조) 35
[그림 3.7] HP2k+1에서 노드 S에 인접한 노드(이미지참조) 36
[그림 3.8] HP2k+2에서 노드 S에 인접한 노드(이미지참조) 37
[그림 3.9] HP5 구조에 포함된 3차원 Pancake HP3 그래프 구조(이미지참조) 38
[그림 3.10] x가 한모듈에 있는 경우 41
[그림 3.11] x가 두모듈에 있는 경우 42
[그림 3.12] n이 홀수인 경우 영역 구분 44
[그림 3.13] n이 짝수인 경우 영역 구분 44