The advent of fast networks and efficient user-level communication protocols has made clusters an attractive alternative to traditional multiprocessor systems. Due to the incremental scalability, cost-effectiveness and high-availability, cluster systems have recently gained increased acceptance as general-purpose multi-programmed computing servers for a variety of scientific and business applications. These applications are generally composed of multiple processes running on distinct CPUs that communicate frequently. Due to the synchronization needs of such applications, performance is greatly hampered if their processes are not scheduled simultaneously on the CPUs. Implicit coscheduling (ICS) is a well-known technique to address this problem in multi-programmed clusters, however, traditional ICS schemes do not incorporate steps to adequately deal with priority boost conflicts, leading to significantly degraded performance.
In this thesis, we propose the use of runtime difference in contention across nodes to provide more sophisticated coscheduling decisions in response to the conflicts. We also present a novel coscheduling scheme termed PROC (Process ReOrdering-based Coscheduling) that adaptively regulates the scheduling sequence of conflicting processes based on the rescheduling latency of their correspondents in remote nodes. We perform extensive simulation-based experiments using both synthetic and realistic workloads to analyze the performance of PROC compared to alternatives such as local scheduling, a widely used batch scheduling, gang scheduling, and existing ICS schemes. The results show that all ICS schemes commonly experience priority boost conflicts, and that the proposed PROC significantly outperforms other ICS alternatives (or batch scheduling) by up to 50.4% (or 72.5%) in the average job response time. This improvement is achieved by reducing wasted idle time and spinning time without sacrificing fairness.
We also present a generic coscheduling framework that can be used to implement any coscheduling algorithm with minimal effort. We demonstrate the flexibility and modularity of this framework by implementing four prior representative ICS coscheduling techniques and our newly proposed PROC schemes on a 16-nodes Linux cluster. According to the experimental results on real machines, we confirm that the proposed PROC approach is very promising, especially for the hunting for wasted idle cycles in clusters, and this is in good agreement with the simulation results.
고성능 네트워크의 발전과 사용자 수준 통신 프로토콜의 등장에 힘입어, 최근 들어 클러스터는 기존의 대규모 멀티프로세서 시스템 (massively parallel processors)을 대체하는 시스템으로 큰 각광을 받고 있다. 또한 가격대비 성능비, 점진적 확장성, 고가용성 등의 장점 때문에, 클러스터 시스템은 다양한 과학계산용 응용 프로그램 뿐만 아니라 엔터프라이즈 응용프로그램들을 동시에 수행할 수 있는 범용의 다중 프로그램화된 (multi-programmed) 컴퓨팅 플랫폼으로 진화하고 있다.
클러스터 시스템에서 수행되는 다양한 응용 프로그램들은 서로 다른 노드에서 실행되는 다수개의 프로세스들로 이루어져 있고, 그 프로세스들 사이의 통신 및 동기화는 일반적으로 매우 빈번하다. 따라서 동기화시에, 프로세스들이 서로 다른 CPU에서 동시에 스케쥴링 되지 않는다면, 클러스터 시스템은 성능상 큰 제약을 드러내게 된다. 다중 프로그램화된 클러스터 환경에서 발생하는 이러한 문제점을 해결하기 위해, 다양한 암묵적 동시 스케쥴링 (implicit coscheduling) 기법들이 제안되었다. 그러나 지금까지 제안된 암묵적 동시 스케쥴링 기법들은 지역 프로세스들 사이에서 발생하는 우선순위 높임 충돌 (priority boost conflict)을 효과적으로 처리하지 못하기 때문에, 심각한 시스템 성능 감소를 가져온다.
본 연구에서는 이러한 우선순위 높임 충돌이 발생했을 때, 좀 더 정교하고 효율적인 동시 스케쥴링을 달성하기 위해서 노드간의 런타임 자원 경쟁 (contention) 상태을 활용하는 새로운 암묵적 동시 스케쥴링 기법, 즉 프로세스 재순서에 기반한 동시 스케쥴링 (process reordering-based coscheduling)을 제안하였다. 제안한 기법의 기본 아이디어는 높임 충돌에 참여하는 프로세스들을 그들과 통신하는 동료 프로세스들이 원격노드에서 재스케쥴링되는 지연시간 (rescheduling latency)을 기반으로 재순서화시키는 것이다. 또한 정확한 재스케쥴링 지연시간 예측을 위해, 프로세스가 CPU를 점유하였을 때 평균적으로 소비하는 시간, 아직 소비되지 않은 메시지를 가진 프로세스의 개수 및 새롭게 준비 (ready) 상태로 전이하는 프로세스의 비율 등을 매개 변수로 하는 작은 오버헤드의 효율적인 예측 휴리스틱을 제안하였다. 제안된 기법의 장점은 프로세스들의 스케쥴링 재순서를 통해 동기화를 필요로 하는 프로세스들간 동기율을 높일 수 있고, 시스템의 자원을 더욱 효과적으로 이용할 수 있다는 것이다.
프로세스 재순서에 기반한 동시 스케쥴링 기법의 성능을 고찰하고, 기존에 제안된 스케쥴링 방법들 (로컬 스케쥴링 기법, 배치 스케쥴링 기법, 갱 스케쥴링 기법 및 기존의 여러 암묵적 동시 스케쥴링 기법들)과의 성능을 비교, 분석하기 위해 우리는 시뮬레이션에 기반한 다양한 시나리오의 실험을 수행하였다. 실험 결과 먼저 암묵적 동시 스케쥴링 기법을 적용한 다중 프로그램화된 클러스터 시스템에서 우선순위 높임 충돌 현상이 매우 빈번하게 발생함을 확인하였다. 또한 제안한 기법이 작업간의 형평성 (fairness)을 유지하면서도 기존의 암묵적 동 시 스케쥴링 기법들보다 평균 작업 반응 시간을 최고 약 50.4%까지 개선시킴을 확인하였다. 그리고 그 성능 개선은 작업의 통신 정도 (communication ratio)와 다중 프로그래밍 개수 (multi-programming level)가 커질수록 더욱 두드러짐을 확인하였다. 이러한 성능 향상은 우선순위 높임 충돌시 로컬 스케쥴러의 잘못된 선택으로 나타나는 불필요한 시스템 유휴시간을 감소시킴으로써 가능해졌다.
또한 본 연구에서는 위의 시뮬레이션 기반의 실험에서 얻어진 성능 결과를 검증하기 위해서 다양한 동시 스케쥴링 정책을 최소한의 노력만으로 현실화할 수 있는 범용의 동시 스케쥴링 프레임워크를 리눅스 클러스터 상에서 구현하였다. 그리고 구현된 프레임워크 상에서 제안한 기법을 포함한 기존의 대표적인 4가지 기법들을 구현하고, 그 성능을 비교, 분석하였다. 이질성 (heterogeneity)을 갖는 16노드의 리눅스 클러스터에서 다양한 실험을 한 결과, 시뮬레이션을 통해서 얻어진 결과와 흡사하게 제안한 방법이 기존의 기법들에 비해 시스템 자원을 매우 효과적으로 사용함을 확인하였다.
