혼합 우선순위 시스템에서 경성 비주기적 태스크 스케쥴링 알고리즘

김형일,이승룡,이종원,김정순(Hyungill Kim),Sungyoung Lee,Jongwon Lee,Jungsoon Kim 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.10

본 논문은 주기적 태스크와 경성 비주기적 태스크가 혼합된 단일 처리기 실시간 시스템 에서 중단형 (preemptive) 경성 비주기적 태스크의 스케쥴링 기법인 자유지역 지시 (Free Region Indicating. FRI) 알고리즘을 제안한다. FRI 알고리즘은 온라인에서 경성 비주기적 태스크에 대하여 할당여부를 판단하며, 주기적 태스크와 비주기적 태스크들에 대하여 고정 우선순위와 가변 우선순위를 혼합한 스케쥴링 기법으로 저자가 개발한 임계 태스크 지시 (Critical Task Indicating: CTI) 알고리즘 [4] 을 확장한 것이다. CTI 알고리즘은 연성 비주기적 태스크 스케쥴링 알고리즘으로, 모의 실험 연구에 의하면 slack stealing 알고리즘 [6] 보다 성능 개선을 이루었으며 특히 시스템 과부하 시에도 잘 작동하였다.FRI 알고리즘은 모든 주기적 태스크의 마감시간을 보장할 뿐 아니라 오프라인에서 작성된 CTI 테이블과 스케쥴링 변동 사항에 대한 정보를 가지고 있는 FRI 테이블을 사용하므로써 알고리즘 수행시간 복잡도를 감소시켰으며 스케쥴링 예측성도 높였다. In this paper, we present a preemptive scheduling of hard-aperiodic task. so called the Free Region Indicating (FRI) algorithm. in jointly scheduling the periodic tasks and hard-aperiodic tasks on a uniprocessor real-time system in which hard deadlines of periodic and aperiodic tasks are scheduled in such a way of mixed scheduling of a fixed and dynamic priority algorithm. The algorithm executes an on-line acceptance test for the hard aperiodic tasks and it has extended the Critical Task Indicator (CTI) algorithm [4]of which simulation study shows a considerable performance improvement over the other soft-aperiodic task scheduling algorithms. such a slack-stealing algorithm [6], especially under a heavy transient overload. The FRI algorithm is not only to guarantee all the deadline of periodic tasks. but also to reduce time complexity and improve scheduling predictability since it maintains both the CTI and FRI tables which have scheduling informations and built off-line.

HCI 기반 의료정보 시스템을 위한 뇌영상의 객체 분류를 이용한 이상 부위 추출

김형일(Hyungil Kim),윤현님(Hyunnim Yoon),김용욱(Yonguk Kim) 한국정보기술학회 2012 한국정보기술학회논문지 Vol.10 No.1

In case medical information systems provide only general image information and medical information, they restrict convenience and efficiency in physicians’ diagnostic and therapeutic activities. In this paper, we propose a HCI-based medical information system that extracts objects suspected to be brain tumor and provides them together with patient information and image information in order to support physicians’ diagnostic and therapeutic activities. This system performed SVM?based object classification using various object characteristics of brain images in order to extract abnormal objects suspected to be brain tumors. The experiment used abnormal objects suspected to be brain tumors, white matter, gray matter, and cerebrospinal fluid, and the experimental results showed the average accuracy of 74.4%.

동적 추천 기능이 있는 음악 추천 서버 구현

김형일 ( Hyungil Kim ),박준태 ( Juntae Park ),김종일 ( Jongil Kim ),김경섭 ( Kyungsup Kim ),김용욱 ( Yonguk Kim ),김준태 ( Juntae Kim ) 한국정보처리학회 2007 한국정보처리학회 학술대회논문집 Vol.14 No.2

본 논문에서는 동적 추천 기능이 있는 자바 기반 음악 추천 서버를 소개한다. 본 논문에서 소개하는 추천 서버는 각 음악 사이의 유사도를 그래프로 저장하는 그래프 기반 협동적 여과 방식을 사용하며, 독립된 서버로 구성되어 클라이언트와 정해진 프로토콜에 따라 통신하도록 구현되었다. 또한 이 추천 서버는 특정 사용자나 특정 음악의 정적인(static) 성향뿐 아니라 시간에 따라 달라지는 동적인(dynamic) 성향에 맞는 추천도 가능하도록 설계되었다. 정적 성향이란 어떤 사용자가 가지고 있는 음악에 대한 기본적인 취향을 나타내고, 동적 성향이란 특정한 상황이나 분위기에 따라 유동적으로 변하는 성향을 의미한다. 본 논문에서 소개하는 추천 서버는 정적 성향과 동적 성향에 대하여 각각 추천할 수 있는 기능을 가지고 있으며, 이러한 기능을 바탕으로 실제 사용자들의 음악 다운로드 데이터를 이용하여 추천 데모 사이트를 구축하였다.

가시성 검사를 이용한 3차원 게임에서의 효율적인 경로 탐색

김형일(Hyungil Kim),정동민(Dongmin Jung),엄기현(Kyhyun Um),조형제(Hyungje Cho),김준태(Juntae Kim) 한국멀티미디어학회 2006 멀티미디어학회논문지 Vol.9 No.11

그래프 기반 협동적 여과를 이용한 음악 추천 시스템

김형일 ( Hyungil Kim ),이진석 ( Jinseok Lee ),이정현 ( Jeonghyun Lee ),조진관 ( Chinkwan Cho ),김경섭 ( Kyoungsup Kim ),김준태 ( Juntae Kim ) 한국정보처리학회 2006 한국정보처리학회 학술대회논문집 Vol.13 No.2

본 논문에서는 각 사용자들의 취향에 맞는 음악을 추천하는 개인화된 음악 추천 시스템을 소개한다. 추천 시스템이란 사용자의 선호도를 분석하고 아이템들에 대한 사용자의 선호도를 예측하여 영화, 음악, 기사, 책, 웹 페이지 등과 같은 아이템들을 추천하는 시스템을 말한다. 추천 시스템들에서 가장 많이 사용하고 있는 협동적 추천 방식은 선호도 데이터를 기반으로 유사한 사용자들을 찾고, 유사 사용자들의 선호도를 기반으로 예측을 수행하는 것으로서, 여러 장점들이 있으나 희소성(sparsity) 문제와 확장성(scalability) 문제에 대해 취약점을 가지고 있다. 아이템들의 전체 수에 비해 매우 적은 수의 아이템 선호도 데이터만 존재한다면 사용자들의 유사도를 계산하기가 어려우며, 또한 사용자의 수가 늘어날수록 유사도 계산에 걸리는 시간이 급격하게 늘어남으로써 수백만 사용자가 있는 웹 사이트 등에서 실시간으로 추천을 수행하기 어렵다. 본 논문에서 소개하는 음악 추천 시스템은 이러한 문제점들을 해결하기 위해 그래프 기반 협동적 여과 기법을 사용한다. 그래프 기반 협동적 여과 기법은 기존의 협동적 여과 기법들과 달리 아이템들 사이의 연관관계를 그래프 모델로 표현하고 저장함으로써 묵시적인 선호도 정보들을 누적하여 희소성 문제를 해결하고, 추천 아이템을 선정하는데 필요한 계산 시간을 크게 단축하여 대규모 데이터에서 실시간 추천을 가능하게 한다는 장점이 있다.

2 단계 결정트리 학습을 이용한 뇌 자기공명영상 분류

김형일(Hyungil Kim),김용욱(Yonguk Kim) 한국정보과학회 2007 정보과학회논문지 : 소프트웨어 및 응용 Vol.34 No.1

본 논문에서는 뇌 자기공명영상을 분류하기 위하여 결정트리 알고리즘을 2 단계로 적용하는 영상 분류 시스템을 제안한다. 영상으로부터 얻을 수 있는 정보에는 두 종류가 있다. 하나는 크기, 색상, 질감, 윤곽선 등 영상으로부터 직접 얻을 수 있는 하위레벨 특징들이고, 다른 하나는 특정 객체의 존재 유무, 여러 부위 사이의 공간적 관계 등 분할된 영상들에 대한 해석을 통해서 얻을 수 있는 상위레벨 특징들이다. 의미에 따라 영상을 분류하기 위해서는 상위레벨 특징들을 기반으로 학습 및 분류가 수행되어야 한다. 제안하는 시스템에서는 결정트리 학습을 각각의 레벨에 개별적으로 적용하며, 하위레벨 분류 결과를 이용하여 상위레벨의 특징을 추출한다. 종양이 있는 뇌 자기공명영상 집합에 대하여 분류 실험을 수행하였으며, 몇 가지 실험 결과를 통해 제안된 시스템의 효과를 확인하였다. In this paper we present a system that classifies brain MR images by using 2 level decision tree learning. There are two kinds of information that can be obtained from images. One is the low-level features such as size, color, texture, and contour that can be acquired directly from the raw images, and the other is the high-level features such as existence of certain object, spatial relations between different parts that must be obtained through the interpretation of segmented images. Learning and classification should be performed based on the high-level features to classify images according to their semantic meaning. The proposed system applies decision tree learning to each level separately, and the high-level features are synthesized from the results of low-level classification. The experimental results with a set of brain MR images with tumor are discussed. Several experimental results that show the effectiveness of the proposed system are also presented.

Sparse 표현을 이용한 이중 에너지 X선 흡수 영상 잡음 제거

김형일 ( Hyungil Kim ),엄원용 ( Wonyong Eom ),김대회 ( Dae Hoe Kim ),노용만 ( Yong Man Ro ) 한국정보처리학회 2012 한국정보처리학회 학술대회논문집 Vol.19 No.1

대사성 골 질환인 골다공증(Osteoporosis)의 조기 진단을 위한 골 밀도를 측정하는 방법이 최근 연구되고 있다. 골 밀도 영상은 이중 에너지 X 선 흡수법에 의해 측정되는데, 영상에 존재하는 잡음은 뼈 영역 추출과 골 밀도 계산에 어려움을 주고 있다. 따라서 본 논문에서는 최근 신호처리 분야에서 폭넓게 사용되고 있는 sparse 표현을 도입하여 X 선 영상의 잡음을 제거하는 방법을 제안한다. 실험을 통해 제안한 잡음 제거 방법의 결과가 기존의 방법에 비해 개선됨을 MSR(Mean to Standard deviation Ratio)과 CNR(Contrast to Noise Ratio)을 통해 확인하였다.

선택적 우선순위 알고리즘 : 가변 우선순위 시스템에서 비주기적 태스크 스케쥴링

김형일(Hyungill Kim),이승룡(Sungyoung Lee),이종원(Jongwon Lee) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.7

슬랙 스틸링 기반 비주기적 태스크 스케쥴링은 슬랙 계산의 복잡도로 인하여 실용적이지 못하다는 문제점을 가지고있다. 이를 개선하기 위하여 본 논문에서는 가변우선순위 시스템 하에서 단순하게 슬랙을 계산할 수 있으며 임계 태스크 지정 (CTI: Critical Task Indicating) 스케쥴링 틀(framework)에서 최적인 선택적 우선순위 (APS: Alternative Priority Scheduling) 연성 비주기적 태스크 스게쥴링 알고리즘을 제안한다. 제안한 알고리즘은 저자가 개발한 EDF-CTI (Earliest Deadline First-Critical Task Indicating) 알고리즘을 확장한 것으로, 오프라인에서 생성한 예측성을 가진 CTI 테이블을 참조하여 온라인에서 우선순위 구동 스케쥴링인 최조 마감 우선순위 (EDF: Earliest Deadline First)와 임계 실행시간 우선 (CEF: Critical Execution time Frist) 스케쥴링 정책을 선택적 (alternatively)으로 적용하는 스케쥴링 기법이다. APS 알고리즘은 슬랙을 계산할 때 낙관적 (optimistic) 슬랙 계산 방식을 사용하는데, 이는 주기적 태스크의 모든 수준에서 슬랙을 계산해야만 하는 슬랙스틸링 기반 알고리즘의 최소 (minimal) 슬랙 계산 방법에 비하여 단순하다. 시뮬레이션 연구결과 제안된 알고리즘은 대부분의 경우 EDF-CTI 알고리즘 및 다른 비주기적 태스크 스케쥴링보다 비슷하거나 더 빠른 반응시간을 나타내었으며 시스템 과부하 상태에서도 잘 동작하였다. The major drawback of the slack stealing based schedulings for aperiodic requests is a high computational complexity to calculate slack which in consequence is considered impractical In order to resolve this problem, we introduce a new type of soft aperiodic task scheduling, called an Alternative Priority Scheduling (APS) Algorithm, which has a simple mechanism to calculate slack and is an optimal within a CTI (Critical Task Indicating) scheduling framework in dynamic: priority systems The APS algorithm has extended the EDF-CTI (Earliest Deadline First-Critical Task Indicating) algorithm developed by the authors The algorithm references the off line built CTI table which is created by the deadlinewise preassignment policy and choices either an EDF or a CEF (Critical Execution time First) algorithm alternatively at on-line. When calculating the slacks, the proposed algorithm uses an optimistic method which is simpler than the minimal slack calculation scheme used in the slack stealing algorithms. The simulation study shows that the proposed algorithm, in most cases, is slightly better than both the EDF-CTI algorithm and the other aperiodic scheduling algorithms in terms of short response time of aperiodic requests, and considerably improves the response time in transient overload.

질의어 의미별 사용자 선호도를 이용한 웹 검색의 성능 향상

김형일(Hyungil Kim),김준태(Juntae Kim) 한국정보과학회 2004 정보과학회논문지 : 소프트웨어 및 응용 Vol.31 No.8

본 논문에서는 웹 검색의 성능 향상을 위해 질의어 의미별 사용자 선호도를 이용한 웹 페이지의 가중치 부여 방식을 제안한다. 일반적으로 검색엔진들은 검색 질의어와 웹 페이지의 어휘 비교에 의한 관련도 측정만을 사용하여 웹 페이지의 가중치를 부여한다. 웹과 같이 방대한 자료를 대상으로 검색을 할 경우 유사한 관련도를 가진 검색 결과가 매우 많으므로 어휘 비교만으로는 중요한 웹 페이지를 선별하기 어렵다. 본 논문에서는 질의어의 의미를 구분하도록 워드넷(WordNet)을 이용한 사용자 인터페이스를 구축하고, 사용자의 클릭 수를 각 웹 페이지의 가중치에 누적함으로써 다수 사용자의 검색 행위에 의한 묵시적 평가가 웹 페이지의 검색 순위에 반영되는 검색 시스템을 구현하였다. 클릭수의 누적에 있어서 질의어 의미별로 가중치를 구분하여 저장함으로써 일반적인 검색엔진보다 정확한 검색이 되었으며, 웹 페이지의 범주별 가중치와 질의어의 의미별 사용자 선호도를 이용함으로써 검색 시스템의 성능을 향상시킬 수 있다는 것을 20개의 어휘에 관련된 41개의 의미들을 대상으로 실험한 결과로 확인하였다. In this paper, we propose a Web page weighting scheme using the user preference in each sense of query word to improve the performance of Web search. Generally search engines assign weights to a web page by using relevancy only, which is obtained by comparing the query word and the words in a web page. In the information retrieval from huge data such as the Web, simple word comparison cannot distinguish important documents because there exist too many documents with similar relevancy. In this paper we implement a WordNet-based user interface that helps to distinguish different senses of query word, and constructed a search engine in which the implicit evaluations by multiple users are reflected in ranking by accumulating the number of clicks. In accumulating click counts, they are stored separately according to senses, so that more accurate search is possible. The experimental results with several keywords show that the precision of proposed system is improved compared to conventional search engines.

협동적 여과를 위한 희소 데이터 변형 기법

김형일(Hyungil Kim),김준태(Juntae Kim) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

협동적 여과를 이용한 추천 시스템은 데이터의 희소성 문제(sparseness problem)와 초기 추천 문제(cold-start problem)에 대해 취약점을 가지고 있다. 협동적 여과를 이용한 추천 시스템에서 사용하는 선호도 데이터에 아이템들의 전체 수량에 비해 매우 적은 양의 아이템 선호도만 존재한다면 사용자들의 유사도 측정에 문제를 발생시켜 극단적인 경우엔 협동적 추천이 불가능할 경우가 발생한다. 이와 같은 문제는 선호도 데이터에 나타난 아이템들의 총수에 비해 사용자가 선호(구매)한 아이템이 극히 적은 수량으로 존재하기 때문이며, 새로운 사용자의 경우에는 아이템 선호도 정보가 전혀 없기 때문에 유사 사용자를 추출하지 못하여 아이템을 전혀 추천할 수 없는 문제가 발생한다. 본 논문에서는 희소성이 높은 선호도 데이터를 희소하지 않은 상태로 변형하는 희소 데이터 변형 기법을 제안한다. 희소 데이터 변형 기법은 희소 데이터에 나타난 사용자와 아이템의 추가 속성 정보의 확률분포를 이용하여 알려지지 않은 선호도 값을 예측함으로써 희소성이 높은 선호도 데이터를 변경하고, 변경된 선호도 데이터를 협동적 추천에 적용하여 추천 성능을 향상시킨다. 이와 같은 선호도 데이터 변경 기법을 데이터 블러링(data blurring)이라 한다. 몇가지 실험 결과를 통해 제안된 기법의 효과를 확인하였다.