MPIRace-Check V 1.0: MPI 병렬 프로그램의 메시지경합 탐지를 위한 도구

박미영 ( Mi Young Park ),정상화 ( Sang Hwa Chung ) 한국정보처리학회 2008 정보처리학회논문지 A Vol.15 No.2

메시지전달 프로그램에서 발생하는 메시지경합은 프로그램의 비결정적 수행결과를 초래하므로 효과적인 디버깅을 위하여 탐지되어야 한다. 메시지경합을 탐지하는 기존의 도구는 임의의 메시지를 수신하는 모든 사건에서 경합이 발생한다고 보고한다. 그러나 메시지들이 전송되는 논리적인 통신채널이 서로 다르면 임의의 메시지를 수신하는 사건에서 경합이 발생하지 않을 수도 있으므로, 기존 도구의 부정확한 탐지정보는 프로그래머의 디버깅 작업을 더욱 어렵게 한다. 본 논문에서는 메시지 송수신 사건간의 병행성과 메시지들의 논리적 통신채널을 검사하여 보다 정확하게 메시지경합을 탐지하는 도구인 MPIRace-Check를 제안하다. 본 도구는 vector timestamp를 이용하여 프로그램 수행 중에 메시지를 전송하는 송수신 사건들간의 병행성을 검사하고, 메시지 부가정보를 이용하여 메시지들의 논리적인 통신채널이 동일한지를 검사하여 메시지경합을 탐지한다. 실험에서는 MPI_RTED와 벤치마크 프로그램을 이용하여 본 도구가 프로그램 수행 중에 효율적으로 모든 경합을 정확하게 탐지함을 보인다. 따라서 본 도구는 메시지경합을 정확하게 탐지하여 프로그래머의 디버깅 부담을 줄이고 신뢰성이 있는 병렬 프로그램의 개발을 가능하게 한다. Message races should be detected for debugging effectively message-passing programs because they can cause non-deterministic executions of a program. Previous tools for detecting message races report that message races occur in every receive operation which is expected to receive any messages. However message races might not occur in the receive operation if each of messages is transmitted through a different logical communication channel so that their incorrect detection makes it a difficult task for programmers to debug programs. In this paper we suggest a tool, MPIRace-Check, which can exactly detect message races by checking the concurrency between send/receive operations, and by inspecting the logical communication channels of the messages. To detect message races, this tool uses the vector timestamp to check if send and receive operations are concurrent during an execution of a program and it also uses the message envelop to inspect if the logical communication channels of transmitted messages are the same. In our experiment, we show that our tool can exactly detect message races with efficiency using MPI_RTED and a benchmark program. By detecting message races exactly, therefore, our tool enables programmers to develop reliable parallel programs reducing the burden of debugging.

메시지 전달 프로그램에서의 수행 중 경합탐지

박미영(Mi-Young Park),강문혜(Moon-Hye Kang),전용기(Yong-Kee Jun),박혁로(Hyuk-Ro Park) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.7·8

메시지전달 프로그램에서 발생하는 메시지경합은 프로그램의 비결정적 수행결과를 초래하므로 효과적인 디버깅을 위하여 탐지되어야 한다. 특히 각 프로세스에서 가장 먼저 발생하는 최초경합은 동일한 프로세스 내에서 다른 경합의 발생을 초래할 수 있으므로, 효과적인 경합탐지를 위해서 우선적으로 탐지되어야 한다. 이러한 경합을 탐지하기 위한 기존의 기법들은 적어도 프로그램을 두 번 수행하거나, 메시지들의 수에 비례한 크기의 추적 파일의 분석을 요구한다. 본 논문은 추적파일을 생성하지 않으면서 단 한번의 프로그램 수행으로 각 프로세스에서 발생하는 최초경합을 탐지하는 기법을 제시하고, 실험을 통해서 본 기법이 최초경합을 정확히 탐지함을 보인다. Message races should be detected for debugging message-passing parallel programs because they can cause non-deterministic executions. Specially, it is important to detect the first race in each process because the first race can cause the occurrence of the other races in the same process. The previous techniques for detecting the first races require more than two monitored runs of a program or analyze a trace file which size is proportional to the number of messages. In this paper we introduce an on-the-fly technique to detect the first race in each process without generating any trace file. In the experiment we test the accuracy of our technique with some benchmark programs and it shows that our technique detects the first race in each process in all benchmark programs.

메시지전달 프로그램의 영향받지 않은 경합조건 탐지를 위한 경합상태 전이기법

박미영(Mi-Young Park),강현석(Hyun-Syug Kang),전용기(Yong-Kee Jun) 한국정보과학회 2006 정보과학회논문지 : 시스템 및 이론 Vol.33 No.8

메시지전달 프로그램에서 발생하는 임의의 메시지경합은 다른 경합의 발생에 영향을 줄 수 있으므로, 효과적인 디버깅을 위해서 영향받지 않은 경합을 탐지하는 것이 중요하다. 이러한 경합을 효율적으로 탐지하기 위한 기존의 기법은 각 프로세스에서 가장 먼저 발생하는 경합의 수신사건에서 수행을 중단하여 경합하는 메시지들을 탐지한다. 그러나 프로세스의 수행 중단은 경합들간에 존재하는 영향관계의 단절을 초래하므로, 탐지된 모든 경합이 영향받지 않은 경합임을 보장하지 못한다. 본 논문은 탐지된 경합의 상태를 프로그램의 수행 종료까지 수신하는 메시지들의 영향 여부에 따라 전이하는 새로운 기법을 제안한다. 본 기법은 경합을 탐지하고 그들간의 영향관계를 프로그램 종료까지 유지하므로, 영향받지 않은 경합만을 효율적으로 탐지한다. Detecting unaffected race conditions is important to debugging message-passing programs effectively, because such a message race can affect other races to occur or not. The previous technique to detect efficiently unaffected races detects racing messages by halting at the receive event of the first race to occur in each process. However this technique does not guarantee that all of the detected races are unaffected, because halting such processes does disconnect some chain of affects-relations among those races. In this paper, we present a novel technique that manages the state of the detected race by examining if every received message is affected until the execution terminates. Our technique therefore guarantees to detect efficiently the unaffected races, because it maintains affects-relations of the races all along the execution of program.

국내 정치인의 목소리 구성요소에 의한 메시지전달력 연구 : 전문가의견과 목소리 분석을 중심으로

정은이 한국정치커뮤니케이션학회 2016 정치커뮤니케이션 연구 Vol.0 No.41

본 연구는 국내정치인의 메시지전달력이 어떠한지를 알기 위해 목소리의 특징이 메시지의 전달력에 영향을 미친다는 사실에 주목하였다. 목소리의 특징을 만들어내는 것은 목소리의 크기, 높이, 음색 등 여러 요인에 따라 다르며, 이러한 요인들은 메시지의 전달력에 영향을 미쳐, 수용자의 메시지 집중 및 호응도, 이해도 등에 영향을 미친다. 이에 본 연구는 국내 정치인의 목소리에 관심을 갖고 연구하였는데, 2017년 대선을 앞두고 있어 세간의 관심을 받고 있는 4명의 정치인을 선정하여 연설시 나타난 목소리를 전문가들의 전문적 의견과 소리스펙트로그램을 활용한 과학적 분석으로 우리 정치인들의 메시지전달력이 어떠한지를 살펴보고, 함의를 도출하고자 하였다. 연구결과로는, 전문가들의 전문의견과 과학적 분석을 통해 목소리의 음높이, 억양변화, 공명, 발음의 정확성 등의 목소리 특징으로 분석대상자의 목소리를 분석하였는데, 현 정치인들의 메시지전달에 있어 보다 심화된 노력이 필요해 보였다. 안정된 음높이로, 듣기에 불편함이 없는 목소리 특징을 보였으나, 메시지 전달에 있어 상당한 영향력을 발휘하는 발음의 정확성에 있어서 부족한 면모를 드러냈다. 이는 메시지의 전달이 불분명하게 이루어질 수 있음을 시사하는 대목이며, 이에 발음의 정확성을 향상시키기 위한 한국정치인들의 목소리 훈련이 진행되기를 바란다. The purpose of this study was to examine the importance of politicians' voices in sending a message. According to previous studies, voice features are influenced by several factors such as tone, pitch, and volume. These factors affect message recipients in responsiveness, understanding, and so on. In this respect, 4 South Korean politicians’ voice features such as vocal pitch, accuracy of pronunciation, resonance, and intonation variation, who are well known for the next presidential election, were investigated in order to evaluate message communicability, using expert opinions and scientific analysis. The results of this study were identified: 1) South Korean politicians were poorer at accurate pronunciation which has a significant impact on message passing. 2) They showed less accuracy in sending a message. Thus, they need to take vocal training course for making their pronunciation more accurate.

Ordering and Processor Assignment for a Parallel Queuing Problem Solver in a Message Passing Environment

Park, Pil Seong 수원대학교 자연과학연구소 1998 자연과학논문집 Vol.1 No.-

자연과학 및 엔지니어링의 많은 모델링 문제들은 크기가 수십만 또는 수백만에까지 이르는 선형 시스템으로 변환한다. 그런 문제의 초병렬 컴퓨터의 등장으로 적절한 시간내에 계산하는 것이 가능해졌는데, 현재 가장 많이 사용되는 병렬 프로그래밍 모델은 message passing이다. 본 논문에서는 Park(1995)에서 제안된 domain decomposition 알고리즘을 소개하고, 그 것의 단점을 수정한 새로운 알고리즘을 제시한다. 또한 이를 message passing 환경에서 구현하기 위해 필요한 그리드 포인트(grid point)의 오더링(ordering)과 프로세서 할당 전략을 고찰하고 그 알고리즘이 수렴함을 보인다.

체크 노드 분할에 의한 LDPC 부호의 새로운 메시지 전달 복호 알고리즘

김성환,장민호,노종선,홍송남,신동준,Kim Sung-Hwan,Jang Min-Ho,No Jong-Seon,Hong Song-Nam,Shin Dong-Joon 한국통신학회 2006 韓國通信學會論文誌 Vol.31 No.4c

본 논문에서는 체크 노드 분할에 의한 low-density parity-check(LDPC) 부호의 새로운 직렬 메시지 전달 복호 알고리즘을 제안한다. 이 새로운 복호 알고리즘은 특히 적은 반복 횟수에 대하여 기존의 메시지 전달 복호 알고리즘의 비트 오율(BER) 성능보다 더 우수한 성능을 보인다. 체크 노드의 분할된 부분 집합의 개수가 증가함에 따라 비트 오율 성능이 보다 좋아진다는 사실을 분석적 결과로 확인할 수 있다. 또한 가우시안 근사화를 이용한 밀도 진화를 이용하여 변수 노드에서 메시지들의 평균값에 대한 재귀 방정식을 유도하고, 모의 실험을 이용하여 분석적인 결과를 검증하였다. In this paper, we propose a new sequential message-passing decoding algorithm of low-density parity-check (LDPC) codes by partitioning check nodes. This new decoding algorithm shows better bit error rate(BER) performance than that of the conventional message-passing decoding algorithm, especially for small number of iterations. Analytical results tell us that as the number of partitioned subsets of check nodes increases, the BER performance becomes better. We also derive the recursive equations for mean values of messages at variable nodes by using density evolution with Gaussian approximation. Simulation results also confirm the analytical results.

Processing-Node Status-based Message Scattering and Gathering for Multi-processor Systems on Chip

Park, Jongsu The Korea Institute of Information and Commucation 2019 Journal of information and communication convergen Vol.17 No.4

This paper presents processing-node status-based message scattering and gathering algorithms for multi-processor systems on chip to reduce the communication time between processors. In the message-scattering part of the message-passing interface (MPI) scatter function, data transmissions are ordered according to the proposed linear algorithm, based on the processor status. The MPI hardware unit in the root processing node checks whether each processing node's status is 'free' or 'busy' when an MPI scatter message is received. Then, it first transfers the data to a 'free' processing node, thereby reducing the scattering completion time. In the message-gathering part of the MPI gather function, the data transmissions are ordered according to the proposed linear algorithm, and the gathering is performed. The root node receives data from the processing node that wants to transfer first, and reduces the completion time during the gathering. The experimental results show that the performance of the proposed algorithm increases at a greater rate as the number of processing nodes increases.

A power-saving 1Gbps Irregular LDPC Decoder based on high-efficiency messagepassing

Wenming Tang,Wen Ji,Xianghui Wei,Takeshi Ikenaga,Satoshi Goto 대한전자공학회 2008 ITC-CSCC :International Technical Conference on Ci Vol.2008 No.7

In this paper we proposed a partially-parallel decoder for irregular LDPC codes from IEEE802.11n standards. Our proposed decoder adopts high-efficiency message-passing algorithm and uses the min-sum algorithm handle the message-passing to reduce the hardware implementation complexity and area, and keep high throughput. Considering reducing the power consumption, we used half-registers and half-memory to store the temporary intrinsic messages. The wasted motion of shiftregister was suppressed. This strategy would save us higher as 30% power under good channel condition. The synthesis result in TSMC 0.18um COMS technology demonstrated that for (1296,324) irregular LDPC code achieved high throughput (1.05Gbps) at the frequency of 200㎒, with 6% area reduction.

On the Low-Complexity Resource Allocation for Self-Healing With Reduced Message Passing in Indoor Wireless Communication Systems

Kisong Lee,Howon Lee,Dong-Ho Cho IEEE 2016 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS Vol.15 No.3

<P>Recently, self-healing has been actively investigated for mitigating an unforeseen network failure. In particular, to enable self-healing operations in indoor wireless communications systems, an autonomous mechanism to resolve unforeseen network failure problems should be considered. Therefore, we here address the issue of autonomous self-healing, in which continuous connectivity can be provided to users by resolving unexpected network failures. To overcome this problem, we propose a low-complexity resource allocation algorithm based on an optimization approach with reduced message passing. In the proposed algorithm, normal base stations perform subchannel and power allocations with a minimum amount of information sharing (N-H(M - 1)) to provide reliable service to users in faulty cells autonomously. We also show that the proposed algorithm converges to a unique fixed point in the low-interference region by using a contraction mapping technique. Through simulation results, we demonstrate that the proposed algorithm achieves good performances with respect to the average cell capacity, user fairness, and outage probability while reducing the message passing overhead and computational complexity.</P>

수직자기기록 채널에서 LDPC를 이용한 메시지 전달 방식의 채널 검출 성능비교

박동혁,이재진 한국통신학회 2008 韓國通信學會論文誌 Vol.33 No.4

수직자기기록 채널에서는 PRML(Partial-Response Maximum Likelihood) 검출방법이나 NPML(Noise-Predictive Maximum Likelihood) 검출방법을 이용한 방식으로 더 이상의 성능 향상을 기대하기 힘들게 되었다. 따라서 LDPCO(Low-Density Parity-Check) 부호를 이용한 성능의 향상을 기대하게 되었는데, 본 논문에서는 메시지 전달 방식을 이용한 채널 검출기와 LDPC 부호를 결합시켜 병렬적으로 채널 반복복호를 수행하여 수직자기기록 채널에서의 성능을 보았다. 또한 메시지 전달 방식의 채널 검출기의 구현 복잡도를 근사화 방식을 이용하여 간단히 하였다.