워크스테이션 네트웍에서의 휴리스틱 태스크 스케줄링 알고리즘

강오한(Oh-Han Kang) 한국정보과학회 2000 정보과학회 컴퓨팅의 실제 논문지 Vol.6 No.6

본 논문에서는 워크스테이션 네트웍 (Network of Workstations) 환경에서 태스크 스케줄링문제를 해결하기 위하여 태스크 중복을 기반으로 하는 휴리스틱 스케줄링 알고리즘을 제안한다. 제안된 알고리즘에서는 NoW에서 통신할 때 발생되는 충돌을 방지하기 위하여 네트웍 통신 자원을 우선 할당하고, 스케줄링 길이를 단축하고 병렬처리 시간을 줄이기 위한 중복 태스크를 선택할 때 휴리스틱을 사용한다. 제안된 알고리즘은 태스크 그래프를 입력으로 받아 NoW 환경의 워크스테이션으로 스케줄링하며, 태스크 그래프에서 노드수가 V일 때 최악의 경우 알고리즘의 시간 복잡도는 O(V²)이다. 제안한 알고리즘을 실제 응용 프로그램의 태스크 그래프에 적용하였다. 시뮬레이션을 통하여 제안된 알고리즘이 스케줄링 길이와 알고리즘에서 요구하는 워크스테이션의 수 관점에서 성능이 향상되었음을 보여준다. In this paper, a task duplication based heuristic scheduling algorithm is proposed to solve the problem of task scheduling on network of workstations (NoW). The proposed algorithm pre-allocates network resources so as to avoid potential communication conflict, and the algorithm uses heuristics to select duplication tasks so as to reduce schedule length and parallel processing time. The algorithm schedules the task of a task graph on to the workstations of a NoW, and worst case time complexity is O(V²), where V is the number of nodes in a task graph. The proposed algorithm has been applied to some practical application DAGs. Simulation results show that the proposed algorithm achieves performance improvement in respect of schedule length and number of workstations required by the algorithm

2015 개정 교육과정에 기초한 중학교 정보 교과서의 탐구성 분석

강오한(Kang Oh-Han) 한국컴퓨터교육학회 2019 컴퓨터교육학회 논문지 Vol.22 No.1

본 연구에서는 2015 개정 교육과정에 기초하여 개발된 중학교 ‘정보’ 교과서의 ‘문제 해결과 프로그래밍’ 단원에 대한 탐구성을 분석하였다. 4종 교과서에 Romey 분석법을 적용하였으며, 4개 분석요소인 본문, 자료, 활동, 평가에 대한 분석을 수행하였다. 연구 결과에 따르면, 본문, 자료, 활동, 평가의 분석요소에서 각각 2종, 3종, 3종, 4종의 교과서가 탐구성이 높은 것으로 나타났다. Romey 지수를 기준으로 2종 교과서의 본문 분석요소가 0.185와 0.413으로 낮게 분포되었으며, 자료 분석요소에서 1종 교과서가 0.147로 매우 낮았다. 활동 분석요소는 4종 교과서 중에서 3종이 0.969, 0.608, 0.627로 높게 나타났다. 평가분석요소는 4종 교과서가 각각 1.333, 1.268, 1.274, 0.764로 매우 높게 나타났다. 그리고 새롭게 개발된 교과서가 이전 교과서보다 탐구성이 향상된 것으로 나타났다. In this research, Problem Solving and Programming - the chapter common among four different types of middle school informatics textbooks based on the national curriculum revised in 2015 - was analyzed to measure its effects on cultivating students" curiosities. Romey"s analysis was applied to these textbooks on four analytic elements - texts, data, activities, and evaluation. The results showed that each type of textbook showed a differing degree of encouraging students" inquisitive tendencies on each analytic element; two out of four textbooks were well developed for texts, three for data, three for activities, and all four for evaluation. In terms of Romey’s index points, two textbooks had low indexes of texts, such as 0.185 and 0.413. Data indices were extremely low in one textbook at 0.147. Three of four textbooks exhibited high indices of activities at 0.969, 0.608 and 0.627. Evaluation indices were high in all four textbooks at 1.333, 1.268, 1.274, and 0.764. These revised textbooks overall showed higher metrics than the previously designed textbooks with regards to promoting students" inquisitive nature.

정보·컴퓨터 중등교사 임용시험의 기출문항 분석

강오한(Oh-Han Kang) 한국컴퓨터교육학회 2018 컴퓨터교육학회 논문지 Vol.21 No.6

본 논문에서는 최근 3년 동안 시행된 정보·컴퓨터 표시과목 임용시험의 기출문항을 13개 기본이수 과목으로 분류하고, 과목별 점수 및 문항수의 구성을 분석하였다. 이와 함께 기본이수과목 중에서 출제비율이 높은 6개 과목에 대해 평가영역별 점수 구성을 분석하였다. 그리고 교과내용학 분야에서 C언어를 사용한 문항들이 차지하는 점수 비중을 조사하였다. 분석 결과에 따르면, 첫째, 교과내용학 분야에서 과목별 점수 비율은 0~17.1%, 문항수 비율은 0~15.8%로 나타났다. 이와 함께 3개 과목은 연도별 점수 편차가 큰 것을 확인하였다. 둘째, 분석 대상 과목들의 평가영역별 점수 비율은 0~52%로 분포되어 영역별로 편차가 큰 것으로 나타났다. 셋째, 최근 3년 동안의 임용시험에서 C언어를 사용한 문항의 점수 비율은 평균 33%로 매우 높게 나타났다. 본 연구에서는 이러한 분석 결과를 바탕으로 개선 방안을 제안하였다. In this paper, questions from the last three years’ appointment examinations for secondary teachers for informatics․computer subjects are classified in a way to fit thirteen basic mandatory courses, for which the composition of scores and the number of questions tested were examined. Of these thirteen basic mandatory courses, questions from six basic mandatory courses with high frequency of assessment were analyzed on their score composition based on the evaluation area. In addition, questions testing knowledge in C language were analyzed separately. The results show scores for the curriculum content subjects ranged from 0% to 17.1%, and the ratio of questions tested from curriculum content subjects 0% to 15.8%. In addition, questions from three courses showed a large deviation in scores for each year. Second, the score composition based on the evaluation area showed a large discrepancy, ranging from 0% to 52.0%. Lastly, the questions tested on the C language exhibited high score on average at 33%. Based on the results from the analysis, this study proposed plans to improve ways to evaluate test takers’ aptitude.

정보 · 컴퓨터 임용시험에서 프로그래밍 문항 분석

강오한(Oh-Han Kang),최정아(Jung-Ah Choi) 한국컴퓨터교육학회 2021 한국컴퓨터교육학회 학술발표대회논문집 Vol.25 No.1(A)

새로운 교육과정이 적용되고 소프트웨어 교육이 강화됨으로써 정보 교과의 전문지식과 함께 프로그래밍 능력을 겸비한 교사를 요구하고 있다. 본 논문에서는 정보·컴퓨터 표시과목의 임용시험에서 프로그래밍 관련 기출문항이 이러한 요구를 수용하고 있는지 분석하였다. 최근 4년 동안의 기출문항을 분석한 결과, C언어를 사용한 문항은 프로그래밍, 알고리즘, 자료구조 과목에서 출제되었으며, 4년 평균 19점이 출제되어 교과내용학 과목 점수의 35%를 차지하는 것으로 나타났다. 프로그래밍 과목의 기출문항에 대한 평가영역별 점수분포를 분석한 결과, C언어의 기본(10점), 배열과 구조체 활용(4점), 함수(12점), 라이브러리 활용(0점)인 것으로 나타났다.

스크래치를 활용한 LT 협동학습이 초등정보영재의 민주시민성에 미치는 영향

강오한(Kang, Oh-Han) 한국과학영재교육학회 2017 과학영재교육 Vol.9 No.1

본 논문에서는 과학영재교육원 초등심화 과정의 30명 학생을 대상으로 12차시 총 36시수의 협동학습을 진행한 후 민주시민성의 변회를 분석하였다. 수업에서는 교육용 프로그래밍 언어인 스크래치의 리믹스 기능을 사용하였으며, LT 모형의 협동학습을 적용하여 최종적으로 팀 단위로 결괴물을 생성하였다. 수엽 전후의 설문결괴를 사용한 t 검증 결과에 따르면, 학습 후 학생들의 민주시민성이 향상되었으며, 통계적으로도 유의마한 것으로 나타났다. 특히 민주시민성에서 준법, 책임, 공동체 영역이 통계적으로 유의마한 차이가 있는 것으로 확인되었다. In the paper, 12 three-hour cooperative learning lessons were given to 30 elementary students from the Science Education Institute for the Gifted and changes in their democratic citizenship was analyzed. The Scratch remix function, an educational programming language, was used in the lessons and each team of the students generated the final results by applying the LT cooperative learning. According to the results of t-test using a survey conducted before and after the classes, the students democratic citizenship was improved after the classes, which was statistically significant. Importantly, there was a statistically significant difference in law-abidingness, responsibility, and community sub-domains of democratic citizenship.

Co-allocation 환경의 그리드 시스템에서 통신비용에 따른 스케줄링 알고리즘의 성능 분석

강오한,강상성,김진석,Kang, Oh-Han,Kang, Sang-Seong,Kim, Jin-Suk 한국정보처리학회 2007 정보처리학회논문지 A Vol.14 No.2

Grid computing, a mechanism which uses heterogeneous systems that are geographically distributed, draws attention as a new paradigm for the next generation operation of parallel and distributed computing. The importance of grid computing concerning communication cost is very huge because grid computing furnishes uses with integrated virtual computing service, in which a number of computer systems are connected by a high-speed network. Therefore, to reduce the execution time, the scheduling algorithm in grid environment should take communication cost into consideration as well as computing ability of resources. However, most scheduling algorithms have not only ignored the communication cost by assuming that all tasks were dealt in one cluster, but also did not consider the overhead of communication cost when the tasks were processed in a number of clusters. In this paper, the functions of original scheduling algorithms are analyzed. More importantly, the functions of algorithms are compared and analyzed with consideration of communication cost within the co allocation environment, in which a task is performed separately in many clusters. 지역적으로 분산되어 있는 이기종의 시스템들을 하나로 묶어 사영하는 그리드 컴퓨팅이 차세대 병렬.분산 연산을 위한 새로운 패러다임으로 관심을 끌고 있다. 고속 네트워크로 연결된 다수의 컴퓨터 시스템이 사용자에게 통합된 가상의 컴퓨팅 서비스를 제공하는 그리드 시스템은 통신비용에 대한 중요성이 매우 크다. 따라서 그리드 환경에서 스케줄링 알고리즘은 작업의 실행시간을 단축하기 위하여 자원들의 연산능력과 함께 통신에 대한 비용을 고려하여야 한다. 그러나 현재까지 발표된 대부분의 스케줄링 알고리듬들은 작업이 한 클러스터에서 처리되는 것을 가정함으로써 통신비용을 무시하였으며, 작업이 다수의 클러스터에 분산되어 처리되는 경우에도 통신비용에 관한 오버헤드를 고려하지 않았다. 본 논문에서는 그리드 시스템에 적합한 기존 스케줄링 알고리즘들의 성능을 분석하였으며, 작업이 다수의 클러스터에 분산되어 수행되는 co-allocation 환경에서 통신비용을 고려하여 알고리즘들의 성능을 비교하고 분석하였다.

WGridSP: 그리드 컴퓨팅을 위한 웹 기반 스케줄링 플랫폼

강오한,강상성,Kang, Oh-Han,Kang, Sang-Seong 한국정보처리학회 2006 정보처리학회논문지 A Vol.13 No.5

본 논문에서는 웹 기반의 그리드 컴퓨팅 환경에서 시스템을 모델링하고 스케줄링 기법을 시뮬레이션 할 수 있는 그리드 스케줄링 플랫폼을 설계하고 구현하였다. 구현한 웹기반 그리드 스케줄링 플랫폼은 자바 환경의 그리드 스케줄링 툴킷인 GridSim을 시뮬레이션 도구로 활용하였으며, 자원 모델링, 작업 모델링, 알고리즘 컴파일, 시뮬레이션, 성능분석을 웹 환경에서 빠르게 수행할 수 있다. 구축한 스케줄링 플랫폼은 향후 그리드 연구에 기반구조로 활용될 수 있으며, 스케줄링 기법의 성능 분석을 위한 도구로 사용될 수 있다. In this paper, we designed and implemented a web-based grid scheduling platform(WGridSP), which can model a system and simulate scheduling scheme in grid computing. WGridSP used GridSim, a grid scheduling toolkit in java-environment, as a tool for simulation and is able to Perform resource modeling, task modeling, algorithm compiling, simulation, and Performance evaluation rapidly in web environment. WGridSP can be applied as a foundation for grid research and can be used to analyze the efficiency of scheduling algorithm.

PC 클러스터에서 스케줄링 기법의 구현

강오한,송희헌,정중수,Kang Oh-Han,Song Hee-Heon,Chung Joong-Soo 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.7

본 논문에서는 버스 기반의 클러스터 구조에 적합한 새로운 태스크 스케줄링 기법을 소개하고, PC 클러스터에 구현하여 스케줄링 기법의 성능을 분석한다. 구현된 스케줄링 기법은 태스크 그래프를 입력으로 받아 PC 클러스터로 스케줄링하며, 휴리스틱을 사용하여 태스크를 선택적으로 중복함으로써 병렬연산시간을 단축한다. PC 클러스터는 리눅스 OS가 설치된 6대의 PC가 Gigabit Ethernet으로 연결되어 있다. 통신을 위해 TCP/IP 프로토콜을 사용하며, 메시지 교환을 위해 표준화된 병렬 프로그래밍 도구로 MPI를 사용한다. 실험을 한 결과 본 논문에서 소개한 스케줄링 기법이 비교 기법보다 병렬연산시간 측면에서 성능이 우수함을 확인하였다. In this-paper, we propose a new task scheduling scheme for bus-based cluster architectures and analyze performance of the scheduling scheme which has been implemented in a PC cluster. The implemented scheme schedules the tasks of a task graph to the processors of a PC cluster, and it reduces parallel execution time by selectively duplicating critical tasks using heuristic. Experimental results show that the proposed scheduling scheme produces better parallel execution time than the other scheduling scheme.

버스 기반의 대칭형 다중프로세서 시스템을 위한 태스크 스케줄링 기법

강오한,김시관,Kang, Oh-Han,Kim, Si-Gwan 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.4

대칭형 다중프로세서(SMP : Symmetric Multiprocessors) 시스템은 고성능의 병렬 연산을 위한 중요하고 효과적인 기반환경을 제공하고 있다. SMP에서 병렬 태스크와 통신을 위한 스케줄링 기법의 선택은 시스템의 성능에 큰 영향을 미치므로 효과적으로 스케줄링 기법에 대한 연구가 필요하다. 본 논문에서는 버스 기반의 SMP를 위한 태스크 중복을 기반으로 하는 스케줄링 기법을 소개한다. 제안한 스케줄링 기법은 잠재하는 통신 충돌을 방지하기 위하여 네트워크 통신 자원을 사전에 할당한다. 제안한 스케줄링 기법의 성능을 비교하기 위하여 프로세서 수와 통신비용의 변화에 대한 스케줄링 길이를 시뮬레이션을 통하여 조사하였다. Symmetric Multiprocessors (SMP) has emerged as an important and cost-effective platform for high performance parallel computing. Scheduling of parallel tasks and communications of SMP is important because the choice of a scheduling discipline can have a significant impact on the performance of the system. In this paper, we present a task duplication based scheduling scheme for bus-based SMP. The proposed scheme pre-allocates network communication resources so as to avoid potential communication conflicts. The performance of the proposed scheme has been observed by comparing the schedule length under various number of processors and the communication cost.

벡터 기반 데이터베이스 및 생성형 AI를 활용한 맞춤형 정보 제공 시스템 개발

강오한(Oh-Han Kang),김현석(Hyeon-Seok Kim),박주원(Ju-Won Park) 한국컴퓨터교육학회 2023 한국컴퓨터교육학회 학술발표대회논문집 Vol.27 No.2