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

최상방(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-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.

항공 통신 기술 : ADS-B 시스템 상태 감시 및 원격 제어 시스템의 설계와 구현

장은미 ( Eun Mee Jang ),송인성 ( In Seong Song ),윤완오 ( Wan Oh Yoon ),최상방 ( Sang Bang Choi ),최상방 ( Sang Bang Choi ) 한국항행학회 2014 韓國航行學會論文誌 Vol.18 No.4

CNS/ATM을 구성하는 감시 시스템의 핵심 기술인 ADS-B는 항공기와 항공기 간의 정보 교환을 통해 기존의 레이더 감시 시스템을 보완 및 대체할 수 있다. ADS-B를 지상 항공 교통 관리 시스템에서 사용할 수 있도록 구축하는 지상 ADS-B 시스템은 항공기와 ADS-B 메시지를 송수신하는 지상장비, ADS-B/TIS-B/FIS-B 서버 등 다양한 장비가 필요하며 이들 장비는 네트워크 기반의 분산 시스템 형태로 구성된다. 따라서 지상 ADS-B 시스템의 분산된 장비들을 효율적으로 관리할 수 있도록 원격에서 지상 ADS-B 시스템을 구성하는 장비들의 상태를 감시하고 제어 할 수 있는 상태 감시 및 원격 제어 시스템이 반드시 필요하다. 본 논문에서는 네트워크 기반 상태 관리 프로토콜인 SNMP를 이용하여 지상 ADS-B 시스템을 구성하는 모든 장비의 상태를 감시하고 제어할 수 있는 ADS-B 시스템 상태 감시 및 원격 제어 시스템을 설계하고 구현하였다. An ADS-B system, which is a critical technology in surveillance area of the CNS/ATM, can replace or compensate a conventional radar based surveillance system through the communications among aircrafts. An ADS-B ground system which is to use the ADS-B on the ground air traffic management system consists of various subsystem devices such as ground stations that communicate with the aircrafts, and ADS-B/TIS-B/FIS-B servers. The ADS-B ground system has a form of distributed system and is interconnected through the network. Therefore, a system which can monitor and control the status of the multiple subsystem devices of the ADS-B ground system is essential. In this paper, we designed and implemented a remote status monitor and control system for the ADS-B system that can monitor and control the subsystem devices of the ADS-B system in remote place via SNMP protocol.

光纎維의 非通信 分野 應用

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

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

배성환(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.

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

배성환(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.

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

김경섭,이윤섭,최상방,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.

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

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

SIMD 프로그래머블 셰이더를 위한 멀티포트 레지스터 파일 설계 및 구현

윤완오(Wan-oh Yoon),김경섭(Kyeong-seob Kim),정진하(Jin-ha Cheong),최상방(Sang-bang Choi) 대한전자공학회 2008 電子工學會論文誌-SD (Semiconductor and devices) Vol.45 No.9

3D 그래픽 알고리즘은 특성상 방대한 양의 스트림 데이터에 대하여 복잡한 연산을 수행하여야 한다. 이러한 알고리즘을 하드웨어에서 신속하게 수행할 수 있는 버텍스 셰이더와 픽셀 셰이더의 도입으로 그래픽 프로세서는 “소프트웨어 셰이더의 하드웨어화”라는 목표를 어느 정도 달성한 것처럼 보이지만, 여전히 Z-버퍼 기반이라는 특정 알고리즘의 틀에서 벗어나지 못하고 있다. 향후 그래픽 프로세서가 궁극적으로 추구하는 모델은 알고리즘에 독립적인 그리고 버텍스 셰이더와 픽셀 셰이더가 통합된 셰이더로 발전할 것이다. 본 논문에서는 프로그래머블 통합 셰이더 프로세서에서 고성능 3차원 컴퓨터 그래픽 영상을 지원하기 위한 멀티포트 레지스터 파일 모델을 설계하고 구현하였다. 설계한 멀티포트 레지스터 파일을 기능적 레벨에서 시뮬레이션을 하여 그 성능을 검증 하였으며, FPGA Virtex-4(xc4vlx200)에 직접 구현하여 하드웨어 리소스 사용율과 속도를 확인 하였다. Characteristically, 3D graphic algorithms have to perform complex calculations on massive amount of stream data. The vertex and pixel shaders have enabled efficient execution of graphic algorithms by hardware, and these graphic processors may seem to have achieved the aim of “hardwarization of software shaders.” However, the hardware shaders have hitherto been evolving within the limits of Z-buffer based algorithms. We predict that the ultimate model for future graphic processors will be an algorithm-independent integrated shader which combines the functions of both vertex and pixel shaders. We design the register file model that supports 3-dimensional computer graphic on the programmable unified shader processor. we have verified the accurate calculated value using FPGA Virtex-4(xcvlx200) made by Xilinx for operating binary files made by the implementation progress based on synthesis results.