MPI 미들웨어에 기반한 병렬검색 시스템 구현

이정훈,박경린 濟州大學校 基礎科學硏究所 2003 基礎科學硏究 Vol.16 No.1

본 논문은 MPI 미들웨어에 기반하여 데이터베이스에 포함되어 웹에 의해 제공되는 정보들을 고속으로 검색할 수 있는 분산병렬 검색 시스템을 구현한다. 지리적으로 산재한 막대한 양의 정보를 다루어야 하는 생물정보 분야 응용의 요구에 부합하기 위하여 LINUX를 탑재한 3대의 PC로 구성된 클러스터를 구축하고 CGI 구동 프로그램, 마스터와 슬레이브로 구서된 MPI 프로세스를 구현하였으며 메시지 큐, MPI 프라미타브, HTTP 1.1 프로토콜에 의해 서로 통신한다. 마스터는 CGI의 요청에 따라 슬레이브에게 명령을 내려 동시에 해당 웹 페이지에 대한 검색을 수행하며 이를 통합하여 CGI에게 전달한다. 마스터는 다수의 CGI 요청들을 직렬화할 뿐 아니라 슬레이브들과의 동기화에 의해 최종적인 검색 결과를 수합한다. 본 논문에서 구현된 클러스터는 특정 어댑터의 추가 구현에 의해 새로운 데이터베이스에 대한 검색 기능을 추가할 수 있으며 동일한 운영체제와 미들웨어를 갖는 노드를 추가함으로써 협력 검색에 있어서 보다 많은 컴퓨터들을 참여 시킬 수 있다. This paper implements a high-speed distributed information retrieval system based on MPI (Massage Passing Interface) middleware. The system is mainly targeted for the biological data stored in a certain type of database software and provided via the web protocol such as HTTP. As the biological data is inherently scattered over the world and has a large volume, the system is built on top of emerging cluster computing architecture, consisting of 3 PC's stuffed with LINUX operating system according to the master-slave paradigm. Each node communicates via message queue. MPI primitive, and HTTP 1.1 protocol. The master node, after being activated via each CGI (Common Gateway Interface) request with the parameter, distributes the search string to the slaves, and combines the partial results from them to produce a final one. An interface adapter to a new web page or remoter database cannot only easily expands the retrieval target to our cluster, but also a new node equipped with same operating system and parallel library can boost the speed of parallel and distributed retrieval.

무선 LAN에 기반한 유비퀴터스 스마트클래스룸의 설계

이정훈,박경린 濟州大學校 基礎科學硏究所 2003 基礎科學硏究 Vol.16 No.1

UBICOMP(ubiquitous computing) 기술을 적용한 스마트 클래스룸(smart classroom)이 향후 새로운 교육환경으로 이용될 것으로 전망됨에 따라 스마트 클래스룸의 구조와 특징을 연구해 보았으며 이러한 스마트 클래스룸 환경에서 요구되는 통신 시스템으로서 IEEE 802.11 무선 LAN 표준이 적합한지 분석하였다. 스마트 클래스룸 내의 트래픽들은 실시간 혹은 비실시간 요구사항을 갖는데 영상과 같은 실시간 트래픽은 비디오 카메라의 특성에 따라, 제어 메시지와 같은 비실시간 트래픽은 실제 수업에 대한 조사에 의해 그 특성이 파악 되었으며 대역폭 할당 기법에 의해 이들은 각각 무선 LAN의 CFP와 CP에 할당되었다. SMPL을 이용한 모의 실험 결과는 주어진 트래픽 인자들에 대해 IEEE 802.11 무선 LAN이 스마트 클래스룸의 트래픽들을 전달하는데 있어서 주기내 전송 보장, 신속한 전달시간 및 대역폭의 효율적 이용 등을 보임으로써 트래픽의 요구사항을 충족시킬 수 있음을 나타낸다. 아울러, 추후 스트림의 대역폭 증가와 트래픽의 증가를 위해서는 네트워크 대역폭의 증가와 아울러 CLS와 같은 부하 조절 기법의 도입 필요성도 제시하고 있다. As we expect a smart classroom based on the notion of ubiquitous computing (UBICOMP) to be used as a new educational environment in the near future, we examined closely its structure and feature and then made analysis on whether IEEE 802.11 wireless LAN standard could be reasonable as a communication system to be built on such smart classroom or not. We measured the characteristics of the traffic within the smart classroom of being expected, which has real-time or non-real-time requirements, through the analysis of motion frames from a video camera in case of real-time traffic such as video data and of an actual classroom work in case of non-real-time traffic such as control messages. Then, we assigned these two types of the traffic to CFP or CP of the wireless LAN respectively using a bandwidth allocation scheme. The simulation results of using SMPL show that IEEE 802.11 wireless LAN can satisfy the requirements of the traffic because we've got the guaranteed transmission within the period, the prompt transmission time, an efficient bandwidth use, and so on, in transmitting the traffic generated by the smart classroom. In addition, we suggest that the adoption of a controlled load scheme in addition to the expansion of network bandwidth be necessary considering that the stream bandwidth and the traffic of the smart class room will increase in the future.

XML 문서의 검색 성능 평가

신인혜,선경희,강순철,박경린 濟州大學校 基礎科學硏究所 2003 基礎科學硏究 Vol.16 No.1

대부분의 사용자들은 자료를 저장하고 검색하기 위하여 관계형 데이터베이스를 사용하여 왔는데, 최근에 차세대 웹문서의 표준으로 주목받고 있는 XML은 데이터베이스와 같이 자료를 표현, 저장, 검색할 수 있는 기능을 가지고 있다. 본 논문에서는 임의로 생성한 검색대상 자료를 데이터베이스에 테이블로 저장하여 검색하는 방법과 XML 문서로 저장하여 검색하는 방법의 검색시간이 성능비교를 행하였다. 성능평가 결과, 검색 파일의 레코드 수가 약 1만개 이하인 경우에는 XML 문서를 이용한 검색이 빨랐고, 그 이상인 경우는 데이터베이스를 이용한 검색 시간이 월등히 빨랐다. XML 관련 검색 파일들을 세부적으로 XML 문서를 저장하는 방법(어트리뷰트로 혹은 엘리먼트)과 C#에서 XML 문서를 읽어드리는 방법(XPath을 혹은 DOM)에 따라 성능평가를 하였는데 XML 문서 작성시 어트리뷰트로 구성하고 마이크로소프트 닷넴 프레임워크에서 제공하는 XPath를 이용하여 XML 문서를 검색하는 방법이 가장 효율적이었다. While most of users have used relational databases to store and search data. XML documents also can represent, store, and search these data like database systems. This paper compares the search time of data in the XML documents with those in database systems. The performance comparison shows that the search time using the XML document is faster than that using database when the number of records is less than then thousand. However, the latter is much faster than the former when the number of records is more than ten thousand. The XML documents can be consist of either using Attributes of Elements. Also, the document can be read either using DOM or XPath. The performance comparison shows that the XML document made up of Attributes and being read using XPath in Microsoft Net Framework provides the fastest search time.

시멘틱 웹 환경에서의 온톨로지 기반의 정보검색

정은경,김영민,변영철,이상준,박경린 濟州大學校 基礎科學硏究所 2003 基礎科學硏究 Vol.16 No.2

온톨로지는 시멘틱 웹을 구현하기 위한 이론이다. 온톨로지는 웹자원의 효과적인 검색, 통합, 재사용을 위한 새로운 기술이고 사람과 이질의 응용 시스템 간에 지식을 공유하고 재사용하기 위한 방법을 제공한다. 온톨로지의 역할은 특별한 개념을 명세화하는 것이다. 도메인과 일반적인 온톨로지는 정보와 지식 시스템을 분석하고 디자인하는 측면에서 공유, 통합, 재사용될 수 있다. 본 연구는 제주도의 숙박과 관광정보를 위한 온톨로지를 디자인하는데 목적이 있다. 그리고 제안된 온톨로지 기반으로 인터넷 웹 검색 시스템을 만드는데 목적이 있다. 본 연구에 의해 클라이언트가 사용하는 표현은 다르지만 뜻이 같은 동의어에 의해 같은 결과를 얻을 수 있다는 것을 알게 되었다. Ontologies are formal theories that are suitable for implementing the semantic web. Which is a new technology that attempts to achieve effective retrieval, integration, and reuse of web resources. Ontologies provide a way of sharing and reusing the knowledge among the people and the heterogeneous application systems. The role of ontologies is that of making explicit specified conceptualizations. In this context, domain and generic ontologies can be shared, reused, and integrated in the analysis and design stage of information and knowledge systems. This study aims to design an ontology for juju lodges and tour, and build an Internet web retrieval system based on the proposed ontologies. This study found that we can take the same result for synonym that cilent use.

Performance Evaluation of Duplication Based Scheduling Algorithms in Multiprocessor Systems

Park, Gyung-Leen 濟州大學校 基礎科學硏究所 2003 基礎科學硏究 Vol.16 No.2

The paper develops the transformation rules in order to use the Stochastic Petri Net model to evaluate the performance of various task scheduling algorithms. The transformation rules are applied to DFRN scheduling algorithm to investigate its effectiveness. The performance comparison reveals that the proposed approach provides very accurate evaluation for the scheduling algorithm when the Communication to Computation Ratio value s small.

다중 처리기 시스템을 위한 효율적인 리스트 스케줄링 알고리즘

박경린(Gyung Leen Park),추현승(Hyun Seung Choo),이정훈(Jeong Hoon Lee) 한국정보처리학회 2000 정보처리학회논문지 Vol.7 No.7

Scheduling parallel tasks, represented as a Directed Acyclic Graph (DAG) or task graph, on a multiprocessor system has been an important research area in the past decades. List scheduling has been a typical approach for solving the problem. List scheduling algorithms assign priorities to a node or an edge in an input DAG, and then generate a schedule according to the assigned priorities. This paper proposes a list scheduling algorithm with effective method of priority assignments. The paper also analyzes the worst case performance and optimality condition for the proposed algorithm. The performance comparison study shows that the proposed algorithm outperforms existing scheduling algorithms especially for input DAGs with high communication overheads. The performance improvement over existing algorithms becomes larger as the input DAG becomes more dense and the level of parallelism in the DAG is increased.

텔레매틱스 기반 컨버전스 서비스 및 기술 동향

박경린(Gyung-Leen Park),이정훈(Junghoon Lee),신인혜(In-Hye Shin) 한국정보과학회 2008 정보과학회지 Vol.26 No.1

Evaluation of Optimal Checkpoint Interval Maximizing Availability

Park, Gyung-Leen,Lee, Bong Kyu,Kim, Chul Soo 濟州大學校 基礎科學硏究所 2003 基礎科學硏究 Vol.16 No.2

폴트 발생시의 회복시간을 감소시키기 위하여 다양한 체크포인트 기법들이 제안되는 동안, 시스템의 가용성을 최대화 시키는 최적의 체크포인트 인터벌을 분석하는 작업은 지난 수 십년 동안 중요한 연구과제였다. 현실을 제한하는 가정 하에 분석적 모델들이 제시되었으나, 체크포인트 기법들이 점점 복잡해짐에 따라서 그 분석적 모델들은 한계를 노출하고 있다. 본 논문은 최적의 체크포인트 인터벌을 찾아내기 위하여 스토캐스틱 페트리 네트를 이용한 성능평가 방법을 제안하고, 실례를 통하여 그 효과성을 검증한다. 본 논문은 널리 쓰이고 있는 두가지 체크포인트 기법 - 유니 프로세스 시스템을 위한 Checkpoint with Rollback Recovery 기법과 멀티 프로세서 시스템을 위한 Primary Site Approch- 에 대한 스토캐스틱 페트리 네트 모델을 제시하고 그 모델들로부터 최적의 체크포인트 인터벌을 찾아내는 방법을 보인다. While various checkpointing schemes have been widely used to reduce the recovery time when a fault occurs, the problem of evaluating the optimal checkpoint interval that maximizes the availability of the system has been a critical research issue for decades. The evaluation can be done by developing analytical models with restrict assumptions. However, the analytical model has reached its limitations as the checkpointing schemes become complicated. This paper proposes to use stochastic Petri net model for the evaluation and shows the effectiveness of the approach using case studies. The paper develops stochastic Petri net models and shows how to obtain the optimal checkpoint intervals for systems employing two widely used checkpointing schemes : Checkpoint with rollback Recovery scheme for uniprocessor systems and Primary Site Approach for multiprocessor systems.

병렬 처리장치의 개수에 따른 스케줄링 알고리즘의 제안 및 성능평가

박경린 ( Gyung-leen Park ),이상준 ( Sang Joon Lee ),이봉규 ( Bongkyu Lee ) 한국인터넷정보학회 2000 인터넷정보학회논문지 Vol.1 No.2

병렬처리 시스템에서의 스케줄링 문제는 응용 프로그램의 병렬 수행 시간을 최소화하는 스케줄을 찾아내는 문제로 지난 수 십년 간 중요한 연구 과제였으며 복제 기반 스케줄링 알고리즘들은 이 문제를 해결하기 위해 제안된 비교적 새로운 접근 방법이다 복제 기반 스케줄링 알고리즘들은 작업들을 복제함으로써 작업들간의 통신비용을 줄이는 방법으로 대부분의 복제 기반 스케줄링 알고리즘들은 무한한 수의 처리장치의 존재를 가정한다 이러한 가정은 현실적이지 못하므로 본 논문은 사용 가능한 처리장치의 수에 따라 다른 스케줄을 생성하는 스케줄링 알고리즘을 제안하고 그 성능을 평가한다 성능 평가 결과는 작업의 수가 N일 경우에 처리장치의 수가 N개 이상이면 무한한 처리장치의 수를 가정하였을 경우와 같은 스케줄을 생성하고 사용 가능한 처리장치의 수가 N개 이하로 감소함에 따라 병렬 수행 시간이 서서히 증가함을 보인다 The scheduling problem in parallel processing systems has been a challenging research issue for decades. The problem is defined as finding an optimal schedule which minimizes the parallel execution time of an application on a target multiprocessor system. Duplication Based Scheduling (DBS) is a relatively new approach for solving the problem, The DBS algorithms are capable of reducing communication overhead by duplicating remote parent tasks on local processors. Most of DBS algorithms assume an availability of the unlimited number of processors in the system. Since the assumption may not hold in practice, the paper proposes a new scalable DBS algorithm for a target system with limited number of processors. It is shown that the proposed algorithm with N available processors generates the same schedule as that obtained by the algorithm with unlimited number of processors, where N is the number of input tasks. Also, the performance evaluation reveals that the proposed algorithm shows a graceful performance degradation as the number of available processors in the system is decreased.

병렬 처리 시스템을 위한 효율적인 복제 중심 스케줄링 알고리즘

박경린(Park Gyung Leen),추현승(Choo Hyun Seung) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.8

Multiprocessor scheduling problem has been an important research area for the past decades. The problem is defined as finding an optimal schedule which minimizes the parallel execution time of an application on a target multiprocessor system. Duplication Based Scheduling (DBS) is a relatively new approach for solving multiprocessor scheduling problems. This paper classifies DBS algorithms into two categories according to the task duplication method used. The paper then presents a new DBS algorithm that extracts the strong features of the two categories of DBS algorithms. The simulation study shows that the proposed algorithm achieves considerable performance improvement over existing DBS algorithms with similar time complexity.