피라미드의 재귀원형군에 대한 임베딩

김숙연(Sook-Yeon Kim),설성욱(Sung-ook Sul),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.3

본 논문에서는 최근 제안된 상호연결망인 재귀원형군에 피라미드를 임베딩하는 방법을 제시하며, 그 임베딩이 여러가지 비용 척도 면에서 최적임을 증명한다. 우선, 최적 팽창률을 갖는 일대일 임베딩을 제시하고, 연장률 2, 밀집률 2임을 보인다. 이 일대일 임베딩을 바탕으로 보다 적은 노드를 갖는 재귀원형군에 대한 최적 부하율의 다대일 임베딩을 제시하고, 연장률이 2임을 보인다. 제시한 일대일 임베딩과 다대일 임베딩은 피라미드의 각 헤라벨에 있는 노드들을 재귀원형군에 균일하게 분포시키며, 이 경우 연장률 2는 최적임을 보인다. 본 논문에서 제안한 임베딩을 이용해 피라미드 구조에서 작동하는 병렬 알고리즘을 재귀원형군 구조의 병렬 컴퓨터에서 효과적으로 사용할 수 있다. In this paper, we present embeddings of the pyramid into the recursive circulant, an interconnection network recently proposed. We also show that the costs of the embeddings are optimal. First, we produce an one-to-one embedding with the expansion of optimum, the dilation of two and the congestion of two, Then we modify this one-to-one embedding to a many-to-one embedding with the load factor of optimum and the dilation of two, These embeddings uniformly distribute the nodes on the same level of the pyramid into the recursive circulant. We also show that the dilation of two is optimal if the embedding distributes the nodes on the same level uniformly, These embeddings can be applied to implement algorithms, designed for pyramids, on a parallel computer of recursive circulant structure.

완전 이진 트리의 재귀 원형군에 대한 Embedding

김숙연(Sook-Yeon Kim),박정흠(Jung-Heum Park),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2

본 논문에서는 divide and conquer 알고리즘을 효율적으로 수행할 수 있는 병렬구조인 완전 이진 트리를 최근에 [4]에서 제안한 병렬 컴퓨터 구조 재귀 원형군(recursive circulant) 에 다대일 embedding하는 문제를 다룬다. 레벨 n인 완전 이진 트리 T_n을 재귀 원형군 G(2^m,4), 1 ≤m≤n-1,에 load factor 가 최적 일때, dilation 2, congestion 2로 embedding할 수 있고 load factor가 최적 load factor+1일때, dilation 1, congestion 2로 embedding할 수 있음을 보인다. 이 결과를 완전 이진 트리에 에지가 첨가된 X-트리나 full ringed 트리에 확장하면 그것들도 load factor 2, dilation 2로 embedding될 수 있다.

에지 고장이 있는 Restricted Hypercube-Like 그래프의 해밀톤 경로

김숙연,전병태,Kim, Sook-Yeon,Chun, Byung-Tae 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.6

Restricted Hypercube-Like(RHL) 그래프는 교차큐브, 뫼비우스큐브, 엠큐브, 꼬인큐브, 지역꼬인큐브, 다중꼬인큐브, 일반꼬인큐브와 같이 유용한 상호연결망들을 광범위하게 포함하는 그래프군이다. 본 논문에서는 $m{\geq}4$ 인 m-차원 RHL 그래프 G에 대해서 임의의 에지 집합 $F{\subset}E(G)$, ${\mid}F{\mid}{\leq}m-2$, 가 고장일 때, 고장 에지들을 제거한 그래프 $G{\setminus}F$는 임의의 서로 다른 두 정점 s와 t에 대해서 dist(s, V(F))${\neq}1$ 이거나 dist(t, V(F))${\neq}1$이면 해밀톤 경로가 있음을 보인다. V(F)는 F에 속하는 에지들의 양 끝점들의 집합이고 dist(v, V(F))는 정점 v와 집합 V(F)의 정점들 간의 최소 거리이다. Restricted Hypercube-Like (RHL) graphs are a graph class that widely includes useful interconnection networks such as crossed cube, Mobius cube, Mcube, twisted cube, locally twisted cube, multiply twisted cube, and generalized twisted cube. In this paper, we show that for an m-dimensional RHL graph G, $m{\geq}4$, with an arbitrary faulty edge set $F{\subset}E(G)$, ${\mid}F{\mid}{\leq}m-2$, graph $G{\setminus}F$ has a hamiltonian path between any distinct two nodes s and t if dist(s, V(F))${\neq}1$ or dist(t, V(F))${\neq}1$. Graph $G{\setminus}F$ is the graph G whose faulty edges are removed. Set V(F) is the end vertex set of the edges in F and dist(v, V(F)) is the minimum distance between vertex v and the vertices in V(F).

무선 센서 네트워크에서 에지 가중치를 이용하여 위치를 측정하는 기법

김숙연,권오흠,Kim Sook-Yeon,Kwon Oh-Heum 한국통신학회 2005 韓國通信學會論文誌 Vol.30 No.10A

무선 센서 네트워크에서 위치측정 문제는 위치가 알려진 일부 고정 노드들을 기준으로 나머지 노드들의 위치를 결정하는 문제이다. 기존의 많은 위치 측정 기법들은 고정 노드들로부터의 거리나 각도의 측정값을 기반으로 multilateration 이나 삼각기법(triangulation)을 사용한다. 본 논문에서는 서로 전송 범위 내에 있는 노드 쌍에 대해서 가중치를 주어 미지 노드들의 위치를 계산하는 새로운 중앙 집중적 알고리즘을 제안한다. 본 기법은 단순하다는 장점을 지니며, 위치 측정 문제가 일차원 행렬 방정식으로 정형화 될 수 있음을 보여준다. 이러한 일차원 행렬방정식이 유일한 해를 가짐을 수학적으로 증명함으로써 모든 미지 노드들의 위치를 유일하게 결정할 수 있음도 보인다. 가중치는 다양하게 설정될 수 있으나 현실적으로 활용될 수 있을 만한 세 가지 가중치 설정 방법을 제시한 후 시뮬레이션을 통해 성능을 비교 분석한다. Localization in wireless sensor networks is to determine the positions of all nodes based on the Down positions of several nodes. Much previous work for localization use multilateration or triangulation based on measurement of angles or distances to the fixed nodes. In this paper, we propose a new centralized algorithm for localization using weights of adjacent nodes. The algorithm, having the advantage of simplicity, shows that the localization problem can be formulated to a linear matrix equalities. We mathematically show that the equalities have a unique solution. The unique solution indicates the locations of unknown nodes are capable of being uniquely determined. Three kinds of weights proposed for practical use are compared in simulation analysis.

크기 2n×2m 인 메쉬의 꼬인 큐브에 대한 임베딩

김숙연 ( Sook Yeon Kim ) 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.4

하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m 에 대하여 크기가 2 × 2m인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 4× 2m인 메쉬가 연장율 1과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 m이 짝수일 경우엔 크기 2ⁿ × 2m인 메쉬가 꼬인 큐브에 연장율 1, 확장율 2n?1로 임베딩됨을 보이고 m이 홀수일 경우엔 연장율 1, 확장율 2ⁿ로 임베딩됨을 보인다 (1≤n≤m). The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even m , a mesh of size 2× 2m can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size 4 × 2m with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size 2ⁿ × 2m can be embedded into a twisted cube with dilation 1 and expansion 2n?1 for even m and with dilation 1 and expansion 2n for odd m where 1≤ n ≤ m.

게이미피케이션을 기반으로 학습동기의 향상을 위한 UX 디자인 연구: 외국어 학습 애플리케이션에서 보상 사례를 중심으로

민재연(Jae Yeon Min),김숙연(Sook Yeon Kim) 한국HCI학회 2021 한국HCI학회 학술대회 Vol.2021 No.1

사회, 문화, 교육 등과 같은 여러 분야에서 발생하는 문제에 대해 게이미피케이션(Gamification)은 게임요소를 적용하여 문제를 해결하는 방법으로 사용되었다. 특히, 교육 분야에서는 학습자의 학습 동기를 유발하여 학습 성과의 향상을 위해 게이미피케이션을 활용하고 있다. 본고는 학습 애플리케이션에서 사용되는 게이미피케이션의 보상 요소가 학습 동기를 향상하기 위해 어떻게 활용되어야 하는지에 대한 UX 디자인 연구를 진행했다. 특히, ARCS 이론을 바탕으로 동기의 향상을 위해 사용되는 보상(Reward) 요인에 대한 사례 분석을 진행했다. 따라서, 본 연구는 학습 분야의 애플리케이션이 게이미피케이션을 활용하여 학습자의 동기를 향상하기 위한 UX 디자인에 대해 제언한다.

크기 2ⁿ ×2^m인 메쉬의 꼬인 큐브에 대한 임베딩

김숙연,Kim, Sook-Yeon 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.4

The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even m, a mesh of size $2{\times}2^m$ can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size $4{\times}2^m$ with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size $2^n{\times}2^m$ can be embedded into a twisted cube with dilation 1 and expansion $2^{n-1}$ for even m and with dilation 1 and expansion $2^n$ for odd m where $1{\leq}n{\leq}m$. 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m 에 대하여 크기가 $2{\times}2^m$인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 $4{\times}2^m$인 메쉬가 연장율 1과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 m 이 짝수일 경우엔 크기 $2^n{\times}2^m$인 메쉬가 꼬인 큐브에 연장율 1, 확장율 $2^{n-1}$ 로 임베딩됨을 보이고 m이 홀수일 경우엔 연장율 1, 확장율 $2^n$로 임베딩됨을 보인다 ($1{\leq}n{\leq}m$).

트래픽 흐름의 분할 전송을 허용하는 통신망에서 경로 보호 메커니즘들에 대한 비교 분석

김숙연(Sook- Yeon Kim),정민영(Min Young Chung),양선희(Sunhee Yang),이유경(Yoo- Kyoung Lee) 한국통신학회 2000 한국통신학회 학술대회논문집 Vol.2000 No.11

다중 메쉬의 꼬인 큐브에 대한 임베딩

김숙연(Sook-Yeon Kim) 한국정보과학회 2010 정보과학회논문지 : 시스템 및 이론 Vol.37 No.2

꼬인 큐브는 병렬처리 시스템의 상호연결망으로서 널리 알려진 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지므로 각광받아 왔다. 본 논문에서는 크기 2ⁿ×2<SUP>m</SUP>인 메쉬의 복사본 2ⁿ?¹ 개가 꼬인 큐브에 노드 중복없이 연장율 1로 임베딩될 수 있음을 보인다(1≤n≤m). 여기서 확장율은 m이 짝수이면 1이고 홀수이면 2이다. The twisted cube has received great attention because it has several superior properties to the hypercube that is widely known as a versatile parallel processing system. In this paper, we show that node-disjoint 2ⁿ?¹ meshes of size 2ⁿ×2<SUP>m</SUP> can be embedded into a twisted cube with dilation 1 where 1≤n≤m. The expansion is 1 for even m and 2 for odd m.

다중 메쉬의 교차큐브에 대한 임베딩

김숙연(Sook-Yeon Kim) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.5

교차큐브는 병렬처리 시스템의 상호연결망으로서 널리 알려진 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지므로 각광 받아 왔다. 크기 4 × 2<SUP>m</SUP>인 메쉬의 복사본 두 개, 혹은 크기 8 × 2<SUP>m</SUP>인 메쉬의 복사본 네 개가 교차큐브에 연장율 1, 확장율 1로 임베딩 될 수 있음이 알려져 있다[Dong, Yang, Zhao, and Tang, 2008]. 그러나 양변의 길이가 모두 8 보다 큰 메쉬 다수 개가 교차큐브에 연장율 1, 확장율 1로 임베딩될 수 있는지는 알려진 바가 없다. 이 논문에서는 크기 2<SUP>n</SUP> × 2<SUP>m</SUP>인 메쉬의 복사본 2<SUP>n-1</SUP> 개가 교차큐브에 연장율 1, 확장율 1로 임베딩될 수 있음을 보인다, n≥ 1, m ≥ 3. 이 연구 결과는 연장율과 확장율이라는 주요 임베딩 측정 척도에서 최적이다. 또한 이 연구결과는 메쉬 구조를 가지는 다수 개의 작업을 교차큐브 구조를 가지는 병렬 컴퓨터에 할당하는데 효과적으로 활용될 수 있다. The crossed cube has received great attention because it has equal or superior properties compared to the hypercube that is widely known as a versatile parallel processing system. It has been known that disjoint two copies of a mesh of size 4 × 2<SUP>m</SUP> or disjoint four copies of a mesh of size 8 × 2<SUP>m</SUP> can be embedded into a crossed cube with dilation 1 and expansion 1 [Dong, Yang, Zhao, and Tang, 2008]. However, it is not known that disjoint multiple copies of a mesh with more than eight rows and columns can be embedded into a crossed cube with dilation 1 and expansion 1. In this paper, we show that disjoint 2<SUP>n-1</SUP> copies of a mesh of size 2<SUP>n</SUP> × 2<SUP>m</SUP> can be embedded into a crossed cube with dilation 1 and expansion 1 where n ≥ 1 and m ≥ 3. Our result is optimal in terms of dilation and expansion that are important measures of graph embedding. In addition, our result is practically usable in allocating multiple jobs of mesh structure on a parallel computer of crossed cube structure.