MIN-based 다중 처리 시스템을 위한 효율적인 병렬 Branch-and-Bound 알고리즘 설계 및 성능 분석

양명국,Yang, Myung-Kook 한국전기전자학회 1997 전기전자학회논문지 Vol.1 No.1

본 논문에서는 다층 연결 구조(Multistage Interconnection Network, MIN)를 기반으로 하는 병렬 컴퓨터 환경에서 효과적으로 운용할 수 있는 병렬 Optimal Best-First search Branch-and-Bound 알고리즘(pobs)을 제안하고, 성능을 분석하였다. 제안된 알고리즘은 먼저 해를 얻고자 하는 문제를 임의의 G개 부 문제로 분할하고 소수 프로세서로 구성된 프로세서 그룹들에 할당하여 각각의 지역 해를 산출하도록 하였다. 따라서 N개의 프로세서를 갖는 시스템은 G개 프로세서 그룹으로 구분되고 각 프로세서 그룹은 P(=N/G)개 프로세서를 보유하게 된다. 각 프로세서 그룹은 할당된 부 문제의 지역 해를 얻는 과정에 병렬 sub-Global Best-First B&B 알고리즘을 수행한다. 프로세서 그룹들이 산출한 지역 해들 가운데 최선의 값을 갖는 지역 해가 문제의 전역 해로 결정되는데, 이를 위하여 각 프로세서 그룹의 대표 프로세서는 할당된 부 문제의 지역 해를 다른 그룹들에게 전파하도록 하였다. 지역 해 전파는 프로세서 그룹들의 지역 해 비교를 통한 전역해 선정 기능과 함께 프로세서 그룹간 작업 불균형 문제를 상당 부분 해소하는 효과를 제공한다. 알고리즘 설계에 이어 성능 평가를 위한 분석 모형을 제시하였다. 제안한 모형은 B&B 알고리즘 수행에 따른 연산 소요시간과 통신 소요시간을 분리하여 처리함으로 병렬 처리 환경에서 보다 실질적인 알고리즘 성능 평가가 가능하게 함과 동시에, 다양한 컴퓨터 연결 구조에서의 알고리즘 성능 예측을 용이하게 하였다. B&B 알고리즘의 확률 특성을 토대로 작성된 성능 분석 연구의 실효성 검토를 위하여 MIN 기반 시스템을 대상으로 병행된 시뮬레이션 결과는 상호 미세한 오차 범위 내에서 일치하는 결과를 보여 제시한 성능 분석 기법의 타당성을 입증하였다. 또한, 본 논문에서 제안한 병렬 알고리즘을 MIN 기반 시스템에 적용하여 기존 알고리즘의 성능과 비교 평가 결과 제안한 pobs가 문제 해결 과정에서 전개되는 부 문제 수를 줄이고 프로세서간의 효율적인 작업 분배 효과를 제공하는 한편 프로세서간의 주된 통신 활동 범위를 국부적으로 제한하여 성능면에서 우수함을 입증하였다. In this paper, a parallel Optimal Best-First search Branch-and-Bound(B&B) algorithm(pobs) is designed and evaluated for MIN-based multiprocessor systems. The proposed algorithm decomposes a problem into G subproblems, where each subproblem is processed on a group of P processors. Each processor group uses tile sub-Global Best-First search technique to find a local solution. The local solutions are broadcasted through the network to compute the global solution. This broadcast provides not only the comparison of G local solutions but also the load balancing among the processor groups. A performance analysis is then conducted to estimate the speed-up of the proposed parallel B&B algorithm. The analytical model is developed based on the probabilistic properties of the B&B algorithm. It considers both the computation time and communication overheads to evaluate the realistic performance of the algorithm under the parallel processing environment. In order to validate the proposed evaluation model, the simulation of the parallel B&B algorithm on a MIN-based system is carried out at the same time. The results from both analysis and simulation match closely. It is also shown that the proposed Optimal Best-First search B&B algorithm performs better than other reported schemes with its various advantageous features such as: less subproblem evaluations, prefer load balancing, and limited scope of remote communication.

Buffered 2 ×2 스위치들로 구성된 다층 연결 망의 Throughput 분석

양명국 울산대학교 1999 공학연구논문집 Vol.30 No.2

본 논문에서는, multiple buffered 2×2 크로스바 스위치들로 구성된 다층 연결 망 (Multistage Interconnection Network, MIN)의 성능 예측 모형을 제안하고, 스위치에 장착된 buffer의 개수 증가에 따른 성능 향상 추이를 분석하였다. Buffered 스위치 기법은 다층 연결 망 내부의 데이터 충돌 문제를 효과적으로 해결할 수 있는 방법으로 널리 알려져 있다. 제안한 성능 예측 모형은 먼저 네트웍 내부 임의 스위치 입력 단에 유입되는 데이터 패킷이 buffered 스위치 내부에서 전송되는 유형을 확률적으로 분석하여 수립되었다. 확률 분석 과정의 수학적 복잡도 절감을 위하여 임의 싸이클 동안 buffer에 저장된 데이터 패킷 관련 확률식 유도 과정 등에 steady state probability 개념을 도입하였다. 제안한 모형은 스위치에 장착된 buffer의 개수와 무관하게 multiple buffered 2×2 크로스바 스위치의 성능 예측이 가능하고, 나아가서 이들로 구성된 모든 종류의 다층 연결 망 성능 분석에 적용이 용이하다. 제안한 수학적 성능 분석 연구의 실효성 검증을 위하여 병행된 시뮬레이션 결과는 상호 4% 이내의 미세한 오차 범위내에서 모형의 예측 데이터와 일치하는 결과를 보여 분석 모형의 타당성을 입증하였다. 또한, 분석 결과 두 개 혹은 네 개의 데이터 패킷을 저장할 수 있는 buffer를 장착한 multiple buffered 2×2크로스바 스위치들로 설계된 8×8 Baseline 네드윅은 각각 83% 및 90%의 Throughput을 제공하는 것으로 관찰되었고, 여덟 개 이상 데이터 패킷을 저장할 수 있는 buffer를 장착한 경우 buffer 개수 증가에 따른 성능 향상 율이 둔화되는 것으로 나타났다. 따라서 buffered 2×2 크로스바 스위치들로 설계된 8×8 Baseline 네트웍의 경우 두 개에서 네 개 가량의 데이터 패킷을 저장할 수 있는 buffer를 스위치에 장착 시키는 것이 효율적인 것으로 추론 되었다. In this paper, a throughput evaluation model of the Multistage Interconnection Networks(MIN) with the multiple buffered 2x2 crossbar switches is proposed and examined. Buffered switch technique is well known to solve the data collision problems of the MIN. The proposed evaluation model is investigated by analyzing the transfer patterns of the data packets that are arrived at the input ports of a switch element in the network. Steady state probability concept is used to simplify the analysis processes. The model not only estimates the performance of the multiple buffered 2x2 crossbar switch with various size of buffers but also can be applied to evaluate MINs which are designed with buffered 2x2 crossbar switches. To validate the proposed evaluation model, the simulation is carried out on a Baseline network that uses the multiple buffered 2x2 crossbar switches Less than 2% error between analysis and simulation results is observed. It is also shown that the 8x8 Baseline networks designed by buffered 2x2 crossbar switches provide 83%, and 90% of throughputs for buffer size of two, and four data packets, respectively. The throughput elevation is significantly reduced as the buffer size increases. This reveals that two to four buffers are optimal for the 8x8 Baseline network with multiple buffered 2x2 crossbar switches.

하이퍼큐브 구조에서의 대용량 데이터 정렬을 위한 병렬 Bitonic 정렬 알고리즘 연구

양명국 울산대학교 1996 공학연구논문집 Vol.27 No.2

데이터 정렬은 다양한 데이터 조작 응용 프로그램의 핵심 요소로 널리 활용되어, 효율 적인 정렬 알고리즘 개발을 위한 연구가 다각도에서 수행되고 있다. Bitonic 정렬 알고리즘은 단계별로 전체 데이터가 데이터 쌍을 형성하고 상호 비교 정렬을 반복하는 특성이 있어, 알고리즘의 병렬화가 용이하고, 대상 병렬 시스템의 상호 연결망 특성에 따라 효과적인 데이터 정렬을 실행할 수 있다. 본 연구에서는 하이퍼규브구조의 상호 연결망이 Bitonic 정렬의 단계별 비교 패턴과 일치하는 점에 착안, 먼저 하이퍼규브 시스템에 Bitonic 정렬 알고리즘을 적용하고, 알고리즘 수행에 소요되는 시간을 분석, 계산하였다. 나아가서 프로세서 개수가 한정된 시스템에서 다량의 데이터를 정렬할 경우 네트워크 내부의 데이터 충돌을 피하고 전체 프로세서 이용률을 최대화시키는 두가지 병렬 Bitonic 정렬 알고리즘(High-Order Interleaving(HOI) 정렬 기법과 Low-Order Interleaving(LOI)정렬기법)을 제안하고, 이들 알고리즘 수행에 소요되는 시간을 구하였다. HOI 방식은 알고리즘이 비교적 단순할 뿐 아니라, 알고리즘 수행에 수요되는 시간도 경제적인 것으로 나타나 성능 면에서 우수한 방식으로 판명되었으나, 응용 분야에서 요구하는 정렬 후 데이터 배열 상태에 따라 정렬 기법이 선택되어야 한다. Data sorting is well known as an elementary process of the various data manipulation problems. Bitonic sorting algorithm is an efficient method to be parallelled due its systematic repetition characteristic of the partial comparison and rearrangement. The comparison pattern of Bitonic sorting is completely match with the Hypercube interconnection. This provides the motivation of this research. Mapping technique of the Bitonic sorting algorithm on a Hypercube system and its time complexity are discussed and calculated. A comparative study is conducted to show the effectiveness of the Hypercube architecture to support the Bitonic sorting algorithm. Two parallel Bitonic algorithms are proposed and analyzed to sort a large data under the limited number of Hypercube connected processors. These are High-Order Interleaving(HOI) Bitonic sorting algorithm and Low-Order interleaving(LOI)Bitonic sorting algorithm. Both algorithms are designed not only to avoid the data collision on the Hypercube network but also to maximize the processor utilization. It is shown that the HOI technique is simple to apply and takes less time to execute the sorting. The selection of algorithm, however, can be determined according to the requirement of the application problems.

편차 적응 퍼지 알고리즘을 이용한 자동 동조 PID 제어에 관한 연구

양명국,이양범 울산대학교 1996 공학연구논문집 Vol.27 No.2

PID 제어는 각종 산업용 기기 제어 분야에서 우수한 기능을 제공하며, 광범위한 제어 시스템에 다양한 방법으로 적용되어, 그 응용 분야가 확장되고있다. 그러나 PID 제어기는 운전 중 발생하는 환경 변화에 적응하기 위하여 수행되는 새로운 동조 이득 값 산출 과정이 매우 난해할 뿐 아리나, 장 시간 동조작업을 요구하므로 현장 운전자에게 과중한 부담을 제공하고 있다. 본 논문에서는 기존의 PID 제어기에 Fuzzy 자동 동조 기법을 이식하여 PID 제어기 동조 작업을 자동으로 수행하도록하는 편차 적응 퍼지 자동 동조 PID 제어기를 설계 제안하고, 이의 성능을 실험으로 입증하였다. 제안된 퍼지 자동 동조기 현장 운전자의 PID 동조 기법을 분석하여 제어계의 입 출력 제어 파라미터를 설정하고, 구체적인 동조 과정 및 다양한 경험적 요소를 기반으로 설계된 퍼지 Rule-base를 근간으로 개발되었다. 드럼 형 65톤 보일러의 수위 및 압력 제어계 PID 제어기에 본 연구에서 개발한 펴지 자동 동조기를 탑재, 장시간 다양한 시뮬레이션을 수행한 결과, 제안한 펴지 자동 동조 PID 제어기는 시스템의 변경된 운전 환경에 따른 최적 이득 값을 산출하여 제어 대상 시스템이 적절한 출력 값을 생성, 유지 하도록하는 성능의 우수성을 보였다. PID control is well-known and widely used technique in various areas of industrial plants due to its verified reliability and control performance. It, howere, requires special knowledge and training with long experiences on plant control as well as the persistent effort to obtain a proper gain. In this paper, an Error Adaptive Fuzzy Auto-Tuning Algorithm where the fuzzy concept is implanted on the PID controllers to tune a PID controller automatically is designed and proposed. The proposed Fuzzy Algorithm is developed based on both the appropriate tuning rules that are investigated from the diverse know-how and experience of experts and the classical PID tuning techniques. The algorithm is simulated on the 65 ton Drum type boiler where the PID controllers are used to control water level and steam pressure of the drum. It has been shown that the proposed algorithm quickly find the optimal tuning point of the PID controller and provides satisfactory on-line transient behavior of the large plants.

고온 고압용 컴팩트 열교환기의 전열성능에 관한 연구

양명국(Myeong-Kuk Yang),임혁(Hyug Lim),현용익(Yong-Ik Hyun),박재홍(Jae-Hong Park),조성열(Sung-Youl Cho),김정규(Jung-Kyu Kim),허인은(In-Eun Hur),고성규(Seong-Kyu Ko),손성기(Seong-Ki Son) 한국마린엔지니어링학회 2009 한국마린엔지니어링학회 학술대회 논문집 Vol.2009 No.-

In view of space saving, the design of more compact heat exchangers is relatively important. Also, to meet the demand for saving energy and resources today, manufacturers are trying to enhance efficiency and reduce the size and weight of heat exchangers. Over the past decade, there has been tremendous advancement in the manufacturing technology of high efficiency heat exchangers. This has allowed the use of smaller and high performance heat exchangers. Consequently, the use of smaller and high performance heat exchanger becomes popular in the design of heat exchangers. Welded compact plate heat exchanger is used in high temperature and pressure. In the design of heat exchanger, it is necessary to understand the heat transfer and frictional characteristics, so performance data are provided to help design of this type heat exchanger.

Daily Load Forecasting Using the Self-Organizing Map

Yang, Myung-Kook,Hwang, Kab-Ju,Cho, Sung-Woo 울산대학교 1998 공학연구논문집 Vol.29 No.2

In this paper, a daily load forecasting algorithm using the self-organizing map(SOM) method is proposed and examined. SOM is a new, powerful software tool for the visualization of high-dimensional data. It requires less training time compared to other networks such as BP learning network, and moreover, its self organizing feature can amend the distorted data. The proposed algorithm analyzes the load patterns of the past couple of years and estimates future load demand by mapping the target day using SOM. KEPCO's hourly load record obtained between 1993 and 1995 is examined to investigate the efficiency of the proposed method. It is shown that the proposed algorithm provides better forecasting results than conventional exponential smoothing method.

출력 버퍼형 a×a 스위치로 구성된 다단 연결 망의 성능 분석

신태지,양명국 한국정보과학회 2002 정보과학회논문지 : 정보통신 Vol.32 No.2

In this paper, a performance evaluation model of the Multistage Interconnection Network(MIN) with the multiple-buffered crossbar switches is proposed and examined. Buffered switch technique is well known to solve the data collision problem of the MIN. The proposed evaluation model is developed by investigating the transfer patterns of data packets in a switch with output-buffers. The performance of the multiple-buffered a×a crossbar switch is analyzed. Steady state probability concept is used to simplify the analyzing processes. Two important parameters of the network performance, throughput and delay, are then evaluated. To validate the proposed analysis model, the simulation is carried out on a Baseline network that uses the multiple buffered crossbar switches. Less than 2% differences between analysis and simulation results are observed. It is also shown that the network performance is significantly improved when the small number of buffer spaces is given. However, the throughput elevation is getting reduced and network delay becomes increasing as more buffer spaces are added in a switch. 본 논문에서는, a×a 출력 버퍼 스위치로 구성된 다단 연결 망(Multistage Interconnection Network, MIN)의 성능 예측 모형을 제안하고, 스위치에 장착된 버퍼의 개수 증가에 따른 성능 향상 추이를 분석하였다. Buffered 스위치 기법은 다단 연결 망 내부의 데이타 충돌 문제를 효과적으로 해결할 수 있는 방법으로 널리 알려져 있다. 제안한 성능 예측 모형은 먼저 네트웍 내부 임의 스위치 입력 단에 유입되는 데이타 패킷이 스위치 내부에서 전송되는 유형을 확률적으로 분석하여 수립되었다. 제안한 모형은 스위치에 장착된 버퍼의 개수와 무관하게 출력 버퍼를 장착한 a×a 스위치의 성능, 즉 네트웍 성능 평가의 두 가지 주요 요소인 네트웍 정상상태 처리율(Normalized Throughput, NT)과 네트웍 지연시간(Network Delay)의 예측이 가능하고, 나아가서 이들로 구성된 모든 종류의 다단 연결 망 성능 분석에 적용이 용이하다. 제안한 수학적 성능 분석 연구의 실효성 검증을 위하여 병행된 시뮬레이션 결과는 상호 미세한 오차 범위 내에서 모형의 예측 데이타와 일치하는 결과를 보여 분석 모형의 타당성을 입증하였다. 또한, 분석 결과 스위치 내부에 많은 버퍼를 장착할수록 정상상태 처리율의 증가율은 감소하고, 네트웍 지연시간은 증가하는 것으로 나타났다.

출력 버퍼형${\alpha}{\times}{\alpha}$스위치로 구성된 다단 연결망의 성능 분석

신태지,양명국 한국정보과학회 2002 정보과학회논문지 : 정보통신 Vol.32 No.2

In this paper, a performance evaluation model of the Multistage Interconnection Network(MIN) with the multiple-buffered crossbar switches is Proposed and examined. Buffered switch technique is well known to solve the data collision problem of the MIN. The proposed evaluation model is developed by investigating the transfer patterns of data packets in a switch with output-buffers. The performance of the multiple-buffered${\alpha}{\times}{\alpha}$ crossbar switch is analyzed. Steady state probability concept is used to simplify the analyzing processes, Two important parameters of the network performance, throughput and delay, are then evaluated, To validate the proposed analysis model, the simulation is carried out on a Baseline network that uses the multiple buffered crossbar switches. Less than 2% differences between analysis and simulation results are observed. It is also shown that the network performance is significantly improved when the small number of buffer spaces is given. However, the throughput elevation is getting reduced and network delay becomes increasing as more buffer spaces are added in a switch. 본 논문에서는, ${\alpha}{\times}{\alpha}$ 출력 버퍼 스위치로 구성된 다단 연결 망(Multistage Interconnection Network, MIN)의 성능 예측 모형을 제안하고, 스위치에 장착된 버퍼의 개수 증가에 따른 성능 향상 추이를 분석하였다. Buffered 스위치 기법은 다단 연결 망 내부의 데이타 충들 문제를 효과적으로 해결할 수 있는 방법으로 널리 알려져 있다. 제안한 성능 예측 모형은 먼저 네트웍 내부 임의 스위치 입력 단에 유입되는 데이타 패킷이 스위치 내부에서 전공되는 유형을 확률적으로 분석하여 수립되었다. 제안한 모형은 스위치에 장착된 버퍼의 개수와 무관하게 출력 버퍼를 장착한 ${\alpha}{\times}{\alpha}$스위치의 성능, 즉 네트웍 성능 평가의 두 가지 주요 요소인 네트웍 정상상태 처리율(Normalized Throughput, NT)과 네트웍 지연시간(Network Delay)의 예측이 가능하고, 나아가서 이들로 구성된 모든 종류의 다단 연결 망 성 분석에 적용이 용이하다. 제안한 수학적 성능 분석 연구의 실효성 검증을 위하여 병행된 시뮬레이션 결과는 상호 미세한 오차 범위 내에서 모형의 예측 데이타와 일치하는 곁과를 보며 분석 모형의 타당성을 입증하였다. 또한, 분석 결과 스위치 내부에 많은 버퍼를 장착할수록 정상상태 처리율의 증가율은 감소하고, 네트웍 지연시간은 증가하는 것으로 나타났다.

출력 버퍼형 $a{\times}b$스위치로 구성된 Fat-tree 망의 성능 분석

신태지,양명국 한국정보과학회 2003 정보과학회논문지 : 정보통신 Vol.30 No.4

본 논문에서는, $a{\times}b$ 출력 버퍼 스위치로 구성된 fat-tree 망의 성능 예측 모형을 제안하고, 스위치에 장착된 버퍼의 개수 증가에 따른 성능 향상 추이를 분석하였다. Buffered 스위치 기법은 스위치 네트웍 내부의 데이타 충돌 문제를 효과적으로 해결할 수 있는 방법으로 널리 알려져 있다. 제안한 성능 예측 모형은 먼저 네트웍 내부 임의 스위치 입력 단에 유입되는 데이타 패킷이 스위치 내부에서 전송되는 유형을 확률적으로 분석하여 수립되었다. 제안한 모형은 스위치에 장착된 버퍼의 개수와 무관하게 출력 버퍼를 장착한 $a{\times}b$ 스위치의 성능, 즉 네트웍 성능 평가의 두 가지 주요 요소인 네트웍 정상상태 처리율(Steady state Throughput, ST)과 네트웍 지연시간(Network Delay)의 예측이 가능하다. 또한 모형의 이해를 도모하기 위하여 지능형 네트워크 트래픽 제어 및 중도 소실 패킷에 대한 다양한 처리 기능 등 최근 개발되는 스위치 네트워크의 부가기능을 배제하고 수식을 정리하였다. 그러나, 제안된 분석 모형은 이들 다양한 성능 향상 기술이 적용된 네트워크, 그리고 다양한 크기의 네트워크 성능분석에도 쉽게 적용이 가능하다. 제안한 수학적 성능 분석 연구의 실효성 검증을 위하여 병행된 시뮬레이션 결과는 상호 미세한 오차 범위 내에서 모형의 예측 데이타와 일치하는 결과를 보여 분석 모형의 타당성을 입증하였다. In this paper, a performance evaluation model of the Fat-tree Network with the multiple-buffered crossbar switches is proposed and examined. Buffered switch technique is well known to solve the data collision problem of the switch network. The proposed evaluation model is developed by investigating the transfer patterns of data packets in a switch with output-buffers. Two important parameters of the network performance, throughput and delay, are then evaluated. The proposed model takes simple and primitive switch networks, i.e., no flow control and drop packet, to demonstrate analysis procedures clearly. It, however, can not only be applied to any other complicate modern switch networks that have intelligent flow control but also estimate the performance of any size networks with multiple-buffered switches. To validate the proposed analysis model, the simulation is carried out on the various sizes of Fat-tree networks that uses the multiple buffered crossbar switches. Less than 2% differences between analysis and simulation results are observed.

핫스팟을 발생시 출력 버퍼형 $a{\times}a$ 스위치로 구성된 다단 연결망의 성능분석

김정윤,신태지,양명국,Kim, Jung-Yoon,Shin, Tae-Zi,Yang, Myung-Kook 한국정보과학회 2007 정보과학회논문지 : 정보통신 Vol.34 No.3

본 논문에서는, $a{\times}a$ 출력 버퍼 스위치로 구성되며 핫스팟이 발생하는 다단 연결 망 (Multistage Interconnection Network, MIN)의 성능 예측 모형을 제안하고, 스위치에 장착된 버퍼의 개수 증가에 따른 성능 향상 추이를 분석하였다. 제안한 성능 예측 모형은 먼저 네트워크 내부의 임의 스위치 입력 단에 유입되는 데이타 패킷이 스위치 내부에서 전송되는 유형을 확률적으로 분석하여 수립되었다. 성능분석 모형은 스위치에 장착된 버퍼의 개수와 무관하게 버퍼를 장착한 $a{\times}a$ 스위치의 성능, 네트워크 정상상태 처리율(Normalized Throughput, NT)과 네트워크 지연시간(Network Delay)의 예측이 가능하고, 나아가서 이들로 구성된 모든 종류의 다단 연결망 성능 분석에 적용이 용이하다. 제안한 수학적 성능 분석 연구의 실효성 검증을 위하여 병행된 시abf레이션 결과는 상호 미세한 오차 범위 내에서 모형의 예측 데이타와 일치하는 결과를 보여 분석 모형의 타당성을 입증하였다. In this paper, a performance evaluation model of the Multistage Interconnection Network(MIN) with the multiple-buffered crossbar switches under Hot-spot environment is proposed and examined. Buffered switch technique is well known to solve the data collision problem of the MIN. The proposed evaluation model is developed by investigating the transfer patterns of data packets in a switch. The performance of the multiple-buffered $a{\times}a$ crossbar switch is analyzed. Steady state probability concept is used to simplify the analyzing processes. Two important parameters of the network performance, throughput and delay, are then evaluated. To validate the proposed analysis model, the simulation is carried out on a Baseline network that uses the multiple buffered crossbar switches. Less than 2% differences between analysis and simulation results are observed. It is also shown that the network performance is significantly improved when the small number of buffer spaces is given. However, the throughput elevation is getting reduced and network delay becomes increasing as more buffer spaces are added in a switch.