고장노드가 있는 하이퍼큐브에서 완전 이진트리의 임베딩 알고리즘

최상방(Sang Bang Choi) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.5

이진트리는 병렬처리 알고리즘에서 자주 사용되며, 이것을 하이퍼큐브에 임베딩하는 방법은 다양하게 응용될 수 있다. 본 논문에서는 완전 이진트리를 고장노드가 있는 하이퍼큐브에 사상하는 병렬 알고리즘을 제안하였다. 제안된 알고리즘은 최대 (n-2)개의 고장노드가 존재하는 n차원 하이퍼큐브에 다일레이션(dilation) 1의 (n-1)-레벨 완전 이진트리를 매우 효율적이며 규칙적으로 임베딩할 수 있다. 제안된 하향식 알고리즘은 병렬로 임베딩이 수행되는 경우 o(n²)의 낮은 시간 복잡도를 갖는다. 실행 시간 중에 발생하는 고장에 대하여는 임베딩된 트리를 국소적으로 재구성할 수 있다. Binary trees have been used frequently in parallel processing algorithms and their embedding on the hypercube is useful for various applications. In this paper, we will propose a parallel scheme which maps complete binary tree to a faulty hypercube. We will show that (n-1)-level complete binary tree with dilation 1 can be embedded in an n-dimensional hypercube with up to n-2 faulty nodes. The proposed top-down algorithm has low time complexity, I.e., O(n₂), using distributed parallel embedding. It also guarantees run-time fault tolerance by reconfiguring the embedded tree locally.

光纎維의 非通信 分野 應用

崔相三(Sang-Sam Choi),宋桂休(Kye-Hyu Song),金明昱(Myung-Ouk Kim),鄭敎龐(Kyo-Bang Chung) 대한전기학회 1984 전기의 세계 Vol.33 No.6

일반화된 회선교환 하이퍼큐브 구조의 재배열성 및 고장허용 능력

최상방(Sang-Bang Choi) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.8

본 논문에서는 재배열 가능한 정적 하이퍼큐브 구조인 일반화된 회선교환 하이퍼큐브 구조를 제안하였다. 제안된 하이퍼큐브에서 두 이웃 노드간의 연결이 2^p, p≥1 링크 쌍(2^p개의 전이중 통신 선로에 해당)으로 연결되어 있으면, 회선교환 방식하에서 2^p개의 서로 독립된 순열을 동시에 처리할 수 있음을 보였다. 만약 각 노드가 2^p개의 PE(processing element)들로 구성되어 있으면, 제안된 하이퍼큐브는 2ⁿ+p개의 PE에 대한 모든 순열을 실현할 수 있다. 본 논문에서는 그러한 순열을 실현할 수 있는 라우팅 알고리듬도 제시하였다. 이러한 하이퍼큐브는 다중 프로세서 시스템을 위한 매우 효율적인 고장허용 재구성 네트워크로 사용될 수 있다. In this paper, we propose a rearrangeable static hypercube architecture called the Generalized Circuit-switching Hypercube. In the proposed hypercube, we show that if each connection between two neightboring nodes consists of 2^p, p≥1, pairs of links (2^p full-duplex communication lines), the hypercube can handle 2^p independent permutations simultaneously in the circuit switching environment. If each node consists of 2p PEs (processing elenments), then the hypercube can realize all permutations of 2ⁿ+p PEs. We also present a routing algorithm to realize those permutations. This hypercube architecture can be used as an efficient fault-tolerant reconfigurable network for multiprocessor systems.

유전 알고리듬을 이용한 멀티 프로세서 시스템의 선형 스케쥴링 알고리듬

배성환(Sung Hwan Bae),최상방(Sang Bang Choi) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.2Ⅳ

The availability of parallel processing systems and computer networks offers a multiple of the processing power, which can be obtained ever from a fast single processor. The objective of multiprocessor scheduling can be stated as finding schedule for allocating tasks onto the processors and their execution time so that task dependence is satisfied and the length of the schedule, known as the parallel time, is minimized The multiprocessor scheduling is a computationally complex problem, described in computer science terms as NP-complete. In this paper, we present a scheduling method based on Genetic Algorithm(GA) for the static scheduling of directed acyclic graphs with consideration of communication costs on homogeneous multiprocessor systems. Basically, the proposed algorithm uses genetic algorithm with a linear scheduling to search a large solution space efficiently and effectively to find the best possible(reasonable) solution.

유전 알고리즘을 이용한 다중프로세서 시스템에서의 선형 스케쥴링 알고리즘 구현

배성환(Sung Hwan Bae),최상방(Sang Bang Choi) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.2

본 논문에서는 유전 알고리즘을 이용하여 다중프로세서 시스템을 위한 선형 스케쥴링 알고리즘을 제안하였다. 일반적으로 유전 알고리즘은 초기세대를 임의로 생성하기 때문에, 문제에 적합하지 않은 개체들의 영향으로 긴 천이시간과 느린 수렴속도를 갖는다. 제안된 알고리즘은 프로세서간의 통신비용을 고려하며, 초기세대를 생성할 때 현재 노드를 기준으로 직접 후임노드만을 동일 프로세서에 할당함으로써 선형 스케쥴링을 하게 되고, 교배연산과 변이연산에서도 기준 노드의 직접 전임노드나 직접 후임노드의 결합을 변화시킴으로써 선형성을 유지하게 된다. 선형 스케쥴링은 비선형에 비해 프로그램의 병렬성을 최대한 활용할 수 있을 뿐 아니라, 코오스 그레인(coarse grain) 방향성 비순환 그래프(directed acyclic graph: DAG)에서 항상 우수한 스케쥴링 결과를 생성한다. 본 논문의 목적은 유전 알고리즘의 실시간 사용 가능성에 중점을 두었으며, 시뮬레이션 결과 제안된 알고리즘은 대부분의 DAG에서 50세대 내의 빠른 수렴속도를 나타내었다. In this paper, we present a linear scheduling method for homogeneous multiprocessor systems using genetic algorithms. In general, genetic algorithms randomly generate initial strings, which leads to long operation time and slow convergence due to an inappropriate initialization. The proposed algorithm considers communication costs among processors and generates initial strings such that successive nodes are grouped into the same cluster. In the crossover and mutation operations, the algorithm maintains linearity in scheduling by associating a node with its immediate successor or predecessor. Linear scheduling can fully utilize the inherent parallelism of a given program and has been proven to be superior to nonlinear scheduling on a coarse grain DAG (directed acyclic graph). This paper emphasizes the usability of the genetic algorithm for real-time applications. Simulation results show that the proposed algorithm rapidly converges within 50 generations in most DAGs.

가변위치 고음성인식 기술을 이용한 무선 홈 네트워크 시스템 구현에 관한 연구

윤준철,최상방,박찬섭,김세영,김기만,강석엽,Yoon, Jun-Chul,Choi, Sang-Bang,Park, Chan-Sub,Kim, Se-Yong,Kim, Ki-Man,Kang, Suk-Youb 한국정보통신학회 2010 한국정보통신학회논문지 Vol.14 No.4

실내 환경에서 음성인식 기술을 이용한 무선 홈 네트워크 시스템 구현에 있어, 잡음과 실내 잔향음은 시스템 성능 저하의 주요 원인이다. 본 연구에서는 실내 인식환경에서 스펙트럼 엔트로피(Spectral entropy) 기반의 음성 구간검출법을 이용하여 잔향음(reverberation) 및 실내잡음에 강인한 음성인식 홈 네트워크 시스템을 구현하고자 한다. 스펙트럼 차감법(Spectral Subtraction)은 잔향으로 인해 왜곡된 신호를 스펙트럼 상에서 제거하여 잔향의 효과를 줄일 수 있고 음성신호와 독립적인 잡음을 제거 할 수 있다. 효과적인 스펙트럼 차감을 위해서는 음성과 비음성 구간의 정확한 구분이 수반되어야 하며 이를 위해서 엔트로피 기반의 음성 구간 검출법을 적용하여 성능을 향상시킨다. 모의 및 실내환경 실험 결과 Spectral entropy 기반의 음성 구간 검출법을 이용할 경우 실내 잔향 및 잡음환경에서 명령어 인식률의 향상이 증명되었다. In realization of wireless home network system using speech recognition in indoor voice recognition environment, background noise and reverberation are two main causes of digression in voice recognition system. In this study, the home network system resistant to reverberation and background noise using voice section detection method based on spectral entropy in indoor recognition environment is to be realized. Spectral subtraction can reduce the effect of reverberation and remove noise independent from voice signal by eliminating signal distorted by reverberation in spectrum. For effective spectral subtraction, the correct separation of voice section and silent section should be accompanied and for this, improvement of performance needs to be done, applying to voice section detection method based on entropy. In this study, experimental and indoor environment testing is carried out to figure out command recognition rate in indoor recognition environment. The test result shows that command recognition rate improved in static environment and reverberant room condition, using voice section detection method based on spectral entropy.

무선 센서 네트워크에서 에너지 효율을 위한 경쟁 구간 단위화 MAC 프로토콜

윤동성(Dong-Sung Yoon),박태신(Tae-Shin Park),송경환(Kyung-Hwan Song),한현석(Hyeon-Seok Han),최상방(Sang-Bang Choi) 대한전자공학회 2017 대한전자공학회 학술대회 Vol.2017 No.11

차량 사용자 인증 시스템을 위한 향상된 충돌 방지 알고리즘의 설계 및 구현

김경섭,이윤섭,최상방,Kim, Kyeong-Seob,Lee, Yun-Seob,Choi, Sang-Bang 한국정보통신학회 2013 한국정보통신학회논문지 Vol.17 No.1

최근 자동차 산업이 눈부시게 발전하면서 운전자의 편의성과 안전성을 위해 차량에는 끊임없이 새로운 시스템이 적용되고 있다. 이러한 시스템은 다수의 FOB 키를 사용하기 때문에 사용자 인증 시 원활한 다중 접속을 위해 충돌방지 알고리즘을 적용시켜 사용하고 있다. 본 논문에서는 다수의 FOB 키를 사용하는 차량용 스마트키 시스템에서 동적으로 사용자 아이디 요청 순서를 최근 사용자 아이디로 변경하여 차후 인증 과정에서의 통신 응답 소요 시간을 획기적으로 감소시키는 향상된 충돌방지 알고리즘을 설계하고 구현하였다. 향상된 충돌방지 알고리즘이 적용된 시스템의 성능 평가를 위해 차량에 실제 장착하여 구현된 알고리즘의 동작을 확인하였고, 다수의 FOB 키에 대한 통신 응답 소요 시간을 측정하였을 때 기존 알고리즘에 비해 약 33% 정도 감소되었음을 검증하였다. Because many of the FOB key, anti-collision algorithm for a seamless multi-access is applied to the smart-key system. In this paper, we have designed and implemented improved anti-collision algorithm that dramatically reduces the communication response time required in the user authentication process immediately after by dynamically changing the order in which the request of the user ID as the user ID on immediately before in the smart key system for vehicles that use many of the FOB key. In order to evaluate the performance of the system the improved anti-collision algorithm is applied, we show the behavior of the algorithm implemented in the state actually mounted on the vehicle and verify that communication response time required for many of the FOB key was reduced by about 33% compared to existing algorithms.

무선 환경에서 병렬 서버를 위한 멀티미디어 전송 및 동기화 기법

신광식,백석균,윤완오,정진하,최상방,Shin Kwang-sik,Baek Seok-Kyun,Yoon Wan-oh,Cheong Jin-ha,Choi Sang-bang 한국통신학회 2005 韓國通信學會論文誌 Vol.30 No.7B

본 논문은 무선 환경에서 병렬서버를 이용한 멀티미디어 전송 및 동기화 기법을 제안한다. 제안된 방법은 MPEG-4 비디오 스트림을 VOP 타입(I-, P-, B-VOP)에 따라 서로 다른 서버에 저장하여 서비스하는 병렬 서버 시스템을 위하여 개발되었다. 이러한 환경의 멀티미디어 전송에 있어서는 특히 부하 불균형, 정체현상, 지터문제를 해결하여야 한다. 따라서 본 연구는 데이터 분할방법, 우선순위 큐, 멀티미디어 동기화 문제에 초점을 맞춘다. 첫째, VOP 타입에 따라 데이터를 분할하여 개별의 서버에 나누어 저장하는 병렬서버 구조를 개발한다. 둘째, 병렬서버 환경에서의 우선순위 알고리즘을 설계한다. 기지국에서는 이 알고리즘의 우선순위에 따라 스케줄링을 수행한다. 마지막으로, 지터를 보상하기 위한 동기화 알고리즘을 설계한다. 기지국은 각 서버로부터 불규칙하게 들어오는 비디오 스트림을 고안된 동기화 알고리즘에 따라 버퍼에 저장한 후, 이동국으로 일정하게 전송한다. 시뮬레이션 분석 결과 기지국이 흔잡한 상황에서 제안한 병렬 서버 구조에 기반을 둔 멀티미디어 스트림 전송 방식이 기존의 방식보다 이동국의 수신 상태가 $57\%$ 향상됐음을 알 수 있다. This paper presents new multimedia transmission and synchronization scheme for parallel server in wireless environment. The proposed scheme is developed for the parallel sewer that stores MPEG-4 data according to VOP (video object plane) types, i.e., I-, p-, and B-VOP. The goal of our research is to develop the enhanced multimedia transmission scheme that copes with load unbalancing, congestion, and jitter. Thus, we consider three issues; the data striping, the priority queuing, and the multimedia synchronization. First, we develop a parallel server architecture in which each server separately stores video data that is striped by the MPEG-4 VOP types.

고상소자 집단화를 이용한 배열구조 메모리의 재구성 알고리듬

김형석(Hyung-sug Kim),최상방(Sang-bang Choi) 대한전자공학회 1994 대한전자공학회 학술대회 Vol.1994 No.7