행렬-스타그래프와 팬케익 및 RFM 그래프는 스타 그래프가 갖는 좋은 성질을 가지면서 하이퍼큐브보다 망 비용이 적은 값을 갖는 상호연결망이다. 행렬-스타그래프는 스타그래프를 기본 모듈로 하여 노드 대칭성, 최대고장허용도, 계층적분할 성질을 갖고 스타그래프보다 망비용이 개선된 상호연결망이다. 본 논문에서는 그래프의 에지 정의를 이용하여 행렬-스타그래프, 팬케익그래프, RFM그래프 사이의 임베딩 방법을 제시한다. 행렬-스타그래프 $MS_{2,n}$은 팬케익그래프 $P_{2n}$에 연장율 4, 확장율 1, $RFM_{n}$그래프는 팬케익그래프 $P_n$에 연장율 2, 확장율 1, 그리고 행렬-스타그래프 $MS_{2,n}$을 $RFM_{2n}$으로 평균연장율 3에 임베딩 가능함을 보인다.
행렬-스타그래프와 팬케익 및 RFM 그래프는 스타 그래프가 갖는 좋은 성질을 가지면서 하이퍼큐브보다 망 비용이 적은 값을 갖는 상호연결망이다. 행렬-스타그래프는 스타그래프를 기본 모듈로 하여 노드 대칭성, 최대고장허용도, 계층적분할 성질을 갖고 스타그래프보다 망비용이 개선된 상호연결망이다. 본 논문에서는 그래프의 에지 정의를 이용하여 행렬-스타그래프, 팬케익그래프, RFM그래프 사이의 임베딩 방법을 제시한다. 행렬-스타그래프 $MS_{2,n}$은 팬케익그래프 $P_{2n}$에 연장율 4, 확장율 1, $RFM_{n}$그래프는 팬케익그래프 $P_n$에 연장율 2, 확장율 1, 그리고 행렬-스타그래프 $MS_{2,n}$을 $RFM_{2n}$으로 평균연장율 3에 임베딩 가능함을 보인다.
Matrix-star, Pancake, and RFM graphs have such a good property of Star graph and a lower network cost than Hypercube. Matrix-star graph has Star graph as a basic module and the node symmetry, the maximum fault tolerance, and the hierarchical decomposition property. Also it is an interconnection netw...
Matrix-star, Pancake, and RFM graphs have such a good property of Star graph and a lower network cost than Hypercube. Matrix-star graph has Star graph as a basic module and the node symmetry, the maximum fault tolerance, and the hierarchical decomposition property. Also it is an interconnection network that improves the network cost against Star graph. In this paper, we propose a method to embed among Matrix-star Pancake, and RFM graphs using the edge definition of graphs. We prove that Matrix-star $MS_{2,n}$ can be embedded into Pancake $P_{2n}$ with dilation 4, expansion 1, and $RFM_{n}$ graphs can be embedded into Pancake $P_{n}$ with dilation 2. Also, we show that Matrix-star $MS_{2,n}$ can be embedded into the $RFM_{2n}$ with average dilation 3.
Matrix-star, Pancake, and RFM graphs have such a good property of Star graph and a lower network cost than Hypercube. Matrix-star graph has Star graph as a basic module and the node symmetry, the maximum fault tolerance, and the hierarchical decomposition property. Also it is an interconnection network that improves the network cost against Star graph. In this paper, we propose a method to embed among Matrix-star Pancake, and RFM graphs using the edge definition of graphs. We prove that Matrix-star $MS_{2,n}$ can be embedded into Pancake $P_{2n}$ with dilation 4, expansion 1, and $RFM_{n}$ graphs can be embedded into Pancake $P_{n}$ with dilation 2. Also, we show that Matrix-star $MS_{2,n}$ can be embedded into the $RFM_{2n}$ with average dilation 3.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
pi-ipi 에서 P, 로 순열을 변환하기 위해 적용할 차원 에지 시퀜스는<戸 2, 戸>이다. 팬케익그래프 P” 의 노드 P에서 차원에 지 시퀜스를 순차적 으로 적용하여 노드 P, 로 도달 가능함을 살펴보자. 첫째, 노드 P에 차원 에지 [尸7] 를 적용한 노드는 _P'T(P)이고, P*p) 의 순열은 pm-2.
가설 설정
&可1刼그래프의 노드 7? 에서 노드 R로 순열을 변환하기 위해 적용할 차원 에지 시퀜스는 <K, 貯>이다?에서 차원 에지 시퀜스를 순차적으로 적용하여 노드 7F로 도달 가능함을 살펴보자. 첫째, 노드 R에 차원 에지 <7?>를 적용한 노드는 RCR)이고, #(/?) 의 순열은 m.mriEl.
제안 방법
증명 RFMn그래프의 노드 /?(=nr2...ri-ir, rM...rn) 에서 에지 발생기 와 尸에 의해 인접한 노드 R, 를 팬케익그래프 & 의 노드 P와 P, 로 각각 사상할 때, 팬케익그래프 R의 에지 정의에 의해 노드 F의 순열에서 노드 户, 의 순열로 변환하는 가장 적은 수의 에지 개수를 통해 연장율을 분석한다. RF" 그래프의 에지 발생기 즉, 차원 에지 "와 歹로 구성되어 있다.
메쉬 구조는 상수 개의 분지수를 갖고 본 논문에서는 스타 그래프 부류로 알려진 행렬-스타(matrixstar) 그래프, 팬케익(pancake)그래프, 그리고 RFM 그래프 사이의 임 베딩을 분석한다. 논문의 구성은 2장에서 본 연구에서 적용되는 그래프의 정의, 종류 및 성질을 그래프 이론 관점에서 알아보고, 3장에서 임 베딩 방법과 연장율을 분석하고, 마지막으로 결론을 맺는다.
병렬 컴퓨터의 위상으로 잘 알려진 스타 그래프는 짧은 지름, 노드 대칭성, 계층적 구조와 최대 고장 허용도 등을 갖는 상호 연결망이다. 본 논문에서는 스타 그래프가 갖는 상호 연결망의 중요한 성질을 가 지면서 망 비용이 개선된 행렬-스타 그래프와 팬케익 그래프, 그리고 그래프 사이의 임 베딩을 분석하였다. 본 연구의 임 베딩 방법은 각 그래프가 동일한 노드 수를 가질 때 그래프의 에지 정의 즉, 에지 생성 규칙을 통해 인접한 두 노드를 사상하고자 하는 대상 그래프에서 사용되는 가장 적은 수의 에지 정의로 표현하였다.
본 논문에서는 스타 그래프가 갖는 상호 연결망의 중요한 성질을 가 지면서 망 비용이 개선된 행렬-스타 그래프와 팬케익 그래프, 그리고 그래프 사이의 임 베딩을 분석하였다. 본 연구의 임 베딩 방법은 각 그래프가 동일한 노드 수를 가질 때 그래프의 에지 정의 즉, 에지 생성 규칙을 통해 인접한 두 노드를 사상하고자 하는 대상 그래프에서 사용되는 가장 적은 수의 에지 정의로 표현하였다. 이때 적용된 에지의 수를 통해 임베 딩에 대한 연장율을 분석하였다.
본 연구의 임 베딩 방법은 각 그래프가 동일한 노드 수를 가질 때 그래프의 에지 정의 즉, 에지 생성 규칙을 통해 인접한 두 노드를 사상하고자 하는 대상 그래프에서 사용되는 가장 적은 수의 에지 정의로 표현하였다. 이때 적용된 에지의 수를 통해 임베 딩에 대한 연장율을 분석하였다. 그래프 정의를 통해 임 베딩 분석이 가능한 이유는 행렬-스타 그래프, 팬 케익그래프, RFA/그래프가 노드 대칭적인 성질이 있기 때문이다.
(그림 4)는 노드가 2행 2열의 행렬 로 표현되는 행렬-스타 그래프 M&2의 예이다. 행렬- 수타 그래프 M&n의 노드는 2n개 원소를 갖는 2행 n 열의 행렬로 표현하므로 본 논문에서는 노드와 행렬을 같은 개념으로 사용한다. 그리고 노드의 주소를 나타내는 25은 노드를 표현하는 행렬이 2행 兀 열을 의미한다.
P2n이 라 할 때, 노드 尸와 F 차원에 지에 의해 인접한 노드 P(P)를 노드 只라 하자. 행렬-스타 그래프 MSm의 노드 X를 팬케익그래 프 此>의 노드 P로 사상하고, 노드 X와 인접한 노드 X'를 팬케익그래프의 노드 p로 사상할 때, 팬케익 그래프의 에지 정의에 의해 노드 P로부터 노드 F로 이동하는 최단 경로의 차원 에지 시퀜스 개수를 통해 임 베딩의 연장율을 알아본다. 행렬-스타 그래프 의 노드를 연결하는 에지에 따라 3가지 경우로 나누어 증명한다.
성능/효과
본 논문의 연구 결과는 행렬-스타 그래프 MS"은 팬케익그래프 尸加에 연장율 4, 확장율 1에 임 베딩 가능하고, 〃그래프는 팬케익그래프 7%에 연장율 2, 확장율 1에 임 베딩 가능함을 보였다. 또한, 행렬- 스타 그래프 을 RFM*으로 임베딩하는 연장율 은 “이고, 평균 연장 율 3에 임 베딩 가능하고, 팬케익 그래프 Pn을 RFMr으로 임베 딩 하는 연장율은 n-1임을 보였다.
P2n이다. 따라서 팬케익그 래프의 노드 尸에서 노드 F'까지 최 단경로 라우팅을 위해 적용해야 할 차원 에지 개수는 4개이므로 연장 율 4임을 알 수 있다.
본 논문의 연구 결과는 행렬-스타 그래프 MS"은 팬케익그래프 尸加에 연장율 4, 확장율 1에 임 베딩 가능하고, 〃그래프는 팬케익그래프 7%에 연장율 2, 확장율 1에 임 베딩 가능함을 보였다. 또한, 행렬- 스타 그래프 을 RFM*으로 임베딩하는 연장율 은 “이고, 평균 연장 율 3에 임 베딩 가능하고, 팬케익 그래프 Pn을 RFMr으로 임베 딩 하는 연장율은 n-1임을 보였다.
노드 ?에서 차원에 지 시 퀜스를 순차적으로 적용하여 노드 F'로 도달 가능함을 살펴보자. 첫째, 노드 P에 차원 에지 < > 를한 노드는 戸CP)이고 순열은 PiPi-1..
※ AI-Helper는 부적절한 답변을 할 수 있습니다.