A heuristic for load balancing on a hypercube multicomputer

우진운Woo, Jin-Woon 檀國大學校 出版部 1991 論文集 Vol.25 No.2

RMESH 구조에서 선형 사진트리의 영역 확장과 스케일링을 위한 상수시간 알고리즘

우진운,Woo, Jin-Woon 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.3

계층적 자료구조인 사진트리는 영상을 표현하는데 매우 중요한 자료구조이다. 사진트리를 메모리에 저장하는 방법 중 선형 사진트리 표현방법은 다른 표현 방법과 비교할 때 저장 공간을 매우 효율적으로 절약할 수 있는 이점이 있기 때문에 사진트리와 관련된 연산의 수행을 위해 선형 사진트리를 사용하는 효율적인 알고리즘 개발에 많은 연구가 진행되어 왔다. 영역 확장은 영상을 주어진 거리만큼 확장시키는 연산이고, 스케일링은 영상을 주어진 크기만큼 증폭시키는 연산으로 영상의 기하학적 연산에 속한다. 본 논문에서는 RMESH(Reconfigulrable MESH) 구조에서 3-차원 n${\times}$n${\times}$n 프로세서를 사용하여 선형 사진트리로 표면된 영상의 영역 확장과 스케일링을 수행하는 효율적인 알고리즘을 제안한다. 이 알고리즘은 n${\times}$n${\times}$n RMESH의 계층구조에서 선형 사진트리의 위치코드들을 효율적으로 전송할 수 있는 기본적인 연산들을 이용함으로써 상수 시간의 시간복잡도를 갖는다. Quadtree, which 11 a hierarchical data structure, is a very important data structure to represent images. The linear quadtree representation as a way to store a quadtree is efficient to save space compared with other representations. Therefore, it has been widely studied to develop efficient algorithms to execute operations related to quadtrees. The region expansion is an operation to expand images by a given distance and the scaling If an operation to scale images by a given scale factor. In this paper, we present algorithms to perform the region expansion and scaling of images represented by quadtrees, using three-dimensional n${\times}$n${\times}$n processors on RMESH(Reconfigurable MESH). These algorithms have constant time complexities by using efficient basic operations to route the locational codes of quadtree on the hierarchical structure of n${\times}$n${\times}$n RMESH.

접미사 배열을 이용한 Suffix-Prefix가 일치하는 모든 쌍 찾기

한선미,우진운,Han, Seon-Mi,Woo, Jin-Woon 한국정보처리학회 2010 정보처리학회논문지 A Vol.17 No.5

Since string operations were applied to computational biology, security and search for Internet, various data structures and algorithms for computing efficient string operations have been studied. The all-pairs suffix-prefix matching is to find the longest suffix and prefix among given strings. The matching algorithm is importantly used for fast approximation algorithm to find the shortest superstring, as well as for bio-informatics and data compressions. In this paper, we propose an algorithm to find all-pairs suffix-prefix matching using the suffix array, which takes O($k{\cdot}m$)?? time complexity. The suffix array algorithm is proven to be better than the suffix tree algorithm by showing it takes less time and memory through experiments. 최근 문자열 연산들이 계산 생물학 및 인터넷의 보안, 검색 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. suffix-prefix가 일치하는 모든 쌍 찾기는 두 개 이상의 문자열이 주어질 때 각 쌍의 문자열에 대해 가장 긴 suffix와 일치하는 prefix를 찾는 것으로 가장 짧은 슈퍼스트링을 검출하는 근사 알고리즘에서 사용될 뿐만 아니라 생물정보학, 데이터 압축 분야에서도 중요하게 사용된다. 본 논문에서는 접미사 배열을 이용하는 suffix-prefix가 일치하는 모든 쌍 찾기 알고리즘을 제안하며 O($k{\cdot}m$) 시간 복잡도를 가진다. 접미사 배열 알고리즘이 접미사 트리 알고리즘 보다 소요 시간과 메모리 면에서 더 우수함을 실험을 통해서 제시한다.

선형 사진트리의 선형이동을 위한 상수시간 RMESH 알고리즘

김경훈,우진운,Kim, Kyung-Hoon,Woo, Jin-Woon 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.3

계층적 자료구조인 사진트리는 이진 영상을 표현하는데 매우 중요한 자료구조이다. 사진트리를 메모리에 저장하는 방법 중 선형사진트리 표현 방법은 다른 표현 방법과 비교할 때 저장 공간을 매우 효율적으로 절약할 수 있는 이점이 있기 때문에 사진트리와 관련된 연산의 수행을 위해 선형 사진트리를 사용하는 효율적인 알고리즘 개발에 많은 연구가 진행되어 왔다. 선형이동은 영상을 주어진 거리만큼 이동시키는 연산으로, 영상 처리의 응용에서 중요하게 사용되는 연산에 속한다. 본 논문에서는 RMESH (Reconfigurable MESH) 구조에서 3-차원 n${\times}$n${\times}$n 프로세서를 사용하여 선형 사진트리로 표현된 이진 영상의 선형 이동을 수행하는 효율적인 알고리즘을 제안한다. 이 알고리즘은 n${\times}$n${\times}$n RMESH의 계층구조에서 선형 사진트리의 위치코드들을 효율적으로 전송할 수 있는 기본적인 연산들을 이용함으로써 상수 시간의 시간 복잡도를 갖는다. Quadtree, which is a hierarchical data structure, is a very important data structure to represent binary images. The linear quadtree representation as a way to store a quadtree is efficient to save space compared with other representations. Therefore, it has been widely studied to develop efficient algorithms to execute operations related with quadtrees. The linear translation is one of important operations in image processing, which moves the image by a given distance. In this paper, we present an algorithm to perform the linear translation of binary images represented by quadtrees, using three-dimensional $n{\times}n{\times}n$ processors on RMESH (Reconfigurable MESH). This algorithm has constant-time complexity by using efficient basic operations to route the locational codes of quardtree on the hierarchical structure of n${\times}$n${\times}$n RMESH.

RMESH구조에서 선형 사진트리의 윈도우 연산을 위한 상수시간 알고리즘

김경훈,우진운,Kim, Kyung-Hoon,Jin, Woon-Woo 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.3

계층적 자료구조인 사진트리는 이진 영상을 표현하는데 매우 중요한 자료구조이다. 사진트리를 메모리에 저장하는 방법 중 선형 사진트리 표현 방법은 다른 표현 방법과 비교할 때 저장 공간을 매우 효율적으로 절약할 수 있는 이점이 있기 때문에 사진트리와 관련된 연산의 수행을 위해 선형 사진트리를 사용하는 효율적인 알고리즘 개발에 많은 연구가 진행되어 왔다. 윈도우 연산은 영상에서부터 윈도우에 표시된 부분 영상을 추출하는 연산으로, 영상 처리의 응용에서 중요하게 사용되는 기하학적 연산에 속한다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 $n{\times}n{\times}n$ 프로세서를 사용하여 선형 사진트리로 표현된 이진 영상의 윈도우 연산을 수행하는 효율적인 알고리즘을 제안한다. 이 알고리즘은 $n{\times}n{\times}n$ RMESH의 계층구조에서 선형 사진트리의 위치코드들을 효율적으로 전송할 수 있는 기본적인 연산들을 이용함으로써 상수 시간의 시간복잡도를 갖는다. Quadtree, which is a hierarchical data structure, is a very important data structure to represent binary images. The linear quadtree representation as a way to store a quadtree is efficient to save space compared with other representations. Therefore, it has been widely studied to develop efficient algorithms to execute operations related with quadtrees. The window operation is one of important geometry operations in image processing, which extracts a sub-image indicated by a window in the image. In this paper, we present an algorithm to perform the window operation of binary images represented by quadtrees, using three-dimensional $n{\times}n{\times}n$ processors on RMESH(Reconfigurable MESH). This algorithm has constant-time complexity by using efficient basic operations to route the locational codes of quardtree on the hierarchical structure of $n{\times}n{\times}n$ RMESH.

문자열의 최장 공통 부분문자열과 최대 반복자를 구하기 위한 상수시간 RMESH 알고리즘

한선미,우진운,Han, Seon-Mi,Woo, Jin-Woon 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.5

문자열 연산이 계산 생물학 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. 최장 공통 부분 문자열 문제는 두 개 이상의 문자열에서 가장 길게 일치하는 부분문자열을 찾는 연산이며, 최대 반복자 문제는 하나의 문자열에서 두 번 이상 반복되는 부분문자열을 찾는 연산이다. 이 연산은 패턴 매칭, 유사도 측정 등의 문자열 처리 분야에서 중요하게 사용되고 있다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 $n{\times}n{\times}n$ 프로세서를 사용하여 두 문자열의 최장 공통 부분문자열을 구하는 알고리즘과 주어진 문자열의 최대 반복자를 찾는 알고리즘을 제안하며, 이 알고리즘들은 모두 O(1) 시간 복잡도를 갖는다. Since string operations were applied to computational biology area, various data structures and algorithms for computing efficient string operations have been studied. The longest common substring problem is an operation to find the longest matching substring in more than two strings, and maximal repeat of string problem is an operation to find substrings repeated more than once in the given string. These operations are importantly used in the string processing area such as pattern matching and likelihood measurement. In this paper, we present algorithms to compute the longest common substring of two strings and to find the maximal repeat of string using three-dimensional $n{\times}n{\times}n$ processors on RMESH(Reconfigurable MESH). Our algorithms have O(1) time complexity.

지능형 에이전트를 이용한 개인화된 유.무선 뉴스 검색 시스템

한선미,우진운,Han, Seon-Mi,Woo, Jin-Woon 한국정보처리학회 2001 정보처리학회논문지B Vol.8 No.6

오늘날 인터넷이 보편화되면서 정보 검색 및 뉴스 검색들이 일반화되고 있지만 엄청난 정보의 양과 다양성 등으로 인해 사용자들은 오히려 정보 검색의 어려움을 호소하고 있다. 이에 본 논문에서는 사용자 편의의 뉴스 검색과 사용자의 요구와 취향이 반영될 수 있도록 BPN(Back Propagation Neural Network)의 학습 기능을 가진 지능형 에이전트를 이용하여 뉴스 기사를 필터링하는 뉴스 검색 시스템을 제안한다. 이 시스템은 여러 신문사의 기사를 수집 및 통합하여 그 날의 주요 기사들을 데이터베이스에 저장하는 수집 에이전트, 사용자가 입력한 키워드를 이용하여 BPN 기법으로 학습시키는 학습 에이전트 등으로 구성되어 있다. 또한 정보 통신 기술의 눈부신 발달로 무선 인터넷이 급속히 보급되는 현실을 감안하여 무선으로도 이러한 서비스를 제공할 수 있도록 시스템을 구성하였다. Today, as the Internet is popularized, information and news retrieval are generalized. However due to the tremendous amount and variety of information, many users appeal the difficulties of information retrieval. Thus in this paper, we propose a news retrieval system, which filters news articles using an intelligent agent with the learning ability of BPN (back propagation neural network). This system also uses a profile to accomodate the personalized news retrieval. This system consists of two major agents, collection agent and learning agent. The collection agent gathers the articles from several news sites, analyzes them, and stores into a database. The learning agent builds the BPN based on the personalized data. In addition, considering the popularity of the wireless internet due to the rapid development of communication technologies, we made this system provide the service through the wireless internet.

RMESH에서 선형 사진트리의 블록 위치 계산을 위한 상수시간 알고리즘

한선미,우진운,Han, Seon-Mi,Woo, Jin-Woon 한국정보처리학회 2007 정보처리학회논문지 A Vol.14 No.3

계층적 자료구조인 사진트리는 영상을 표현하는데 매우 중요한 자료구조이다. 사진트리를 메모리에 저장하는 방법 중 선형 사진트리 표현 방법은 다른 표현 방법과 비교할 때 저장 공간을 매우 효율적으로 절약할 수 있는 이점이 있기 때문에 사진트리와 관련된 연산의 수행을 위해 선형 사진트리를 사용하는 효율적인 알고리즘 개발에 많은 연구가 진행되어 왔다. 블록위치 계산은 영상에서부터 주어진 블록을 완전히 포함하는 컴포넌트를 추출하는 연산으로, 영상 처리의 응용에서 중요하게 사용되는 기하학적 연산에 속한다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 $n\times n\times n$ 프로세서를 사용하여 선형 사진트리로 표현된 영상의 블록위치를 계산하는 상수시간 알고리즘을 제안한다. 이 알고리즘은 $n\times n\times n$ RMESH의 계층구조에서 선형 사진트리의 위치코드들을 효율적으로 처리하는 기본적인 연산들을 이용함으로써 상수시간의 시간복잡도를 갖는다. Quadtree, which is a hierarchical data structure, is a very important data structure to represent images. The linear quadtree representation as a way to store a quadtree is efficient to save space compared with other representations. Therefore, it has been widely studied to develop efficient algorithms to execute operations related with quadtrees. The computation of block location is one of important geometry operations in image processing, which extracts a component completely including a given block. In this paper, we present a constant time algorithm to compute the block location of images represented by quadtrees, using three-dimensional $n\times n\times n$ processors on RMESH(Reconfigurable MESH). This algorithm has constant-time complexity by using efficient basic operations to deal with the locational codes of quardtree on the hierarchical structure of $n\times n\times n$ RMESH.

딥러닝 기반의 전자광학위성 다중밴드 이미지 생성 방법

김신욱(Shinwook Kim),육영춘(Youngchun Youk),허행팔(Haeng-Pal Heo) 한국항공우주학회 2021 한국항공우주학회 학술발표회 논문집 Vol.2021 No.11

손상된 하이퍼큐브상의 메세지 라우팅 알고리즘

공헌택(Kong Heon Taek),우진운(Woo Jin Woon) 한국정보처리학회 1996 정보처리학회논문지 Vol.3 No.2

Communications on hypercube nodes are done by done by explicit message routing. So efficient message routing is very important for the performance of hypercube multicomputers. However, hypercube nodes can be faulty due to hardware and/or software problems, which is called an injured hypercube. A reliable hypercube system should tolerate the problems. One of the methods to enhance reliability on injured hypercube is to use fault-tolerant message routing algorithms. In this paper, we propose a message routing algorithm with possible shortest distance using disjoint paths. To analyze the performance, the algorithm is simulated and evaluated.