KR101262679B1

KR101262679B1 - 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치

Info

Publication number: KR101262679B1
Application number: KR1020130015568A
Authority: KR
Inventors: 송형근; 오유근; 지정우; 이규성
Original assignee: 송형근; 이규성; 지정우; 오유근
Priority date: 2013-02-13
Filing date: 2013-02-13
Publication date: 2013-05-20
Anticipated expiration: 2033-02-13
Also published as: US20140229621A1; US9203778B2; WO2014126322A1

Abstract

클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치가 개시된다. 일 실시예에 따른 자원 배분 장치는 처리되어야 하는 태스크(task) 및 태스크에 사용되는 자원에 대한 정보를 수집하는 자원 정보 수집부 및 정보에 따라 IVSCD(Initial Value Setting and Cycle Deletion)를 이용하여 유틸리티가 증가되도록 태스크를 자원에 분배하는 자원 분배부를 포함한다.

Description

클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치{DEVICE TO ALLOCATE RESOURCE EFFECTIVELY FOR CLOUD COMPUTING}

클라우드 컴퓨팅에 있어서 IVSCD(Initial Value Setting and Cycle Deletion)를 이용하여 자원을 효율적으로 배분하는 장치를 개시한다.

클라우드 컴퓨팅(cloud computing)은 인터넷 상의 서버를 기반으로 하는 컴퓨팅 기술을 말한다. 이를 이용한 클라우드 서비스(cloud service)에는 세가지 유형이 있는데, 인프라를 제공하는 Infrastructure as a Service (IaaS), 플랫폼을 제공하는 Platform as a Service (PaaS), 마지막으로 소프트웨어를 제공하는 Software as a Service (SaaS)이다.

IaaS의 경우 주로 가상화 기능을 활용하지만 물리 자원을 기반으로 가상화 된 가상 자원을 관리한다. PaaS는 서비스를 호스팅하고 운영하는 환경에서 각 서비스의 자원 활용 상태와 클러스터 시스템의 현재 상태를 기반으로 최상의 자원 활용성과 확장성, 서비스 안정성을 제공한다. 여기서 자원이란 일반적으로 사용자의 전산계산, 데이터 저장, 온라인 서비스 등을 도와 주는 도구를 의미한다. 예를 들어, 가상PC(실제 PC의 일부), 실제 PC, RAID 디스크, 웹 호스팅 용 전용 서버 클러스터, 대규모 클러스터 시스템의 일부 등을 의미한다.

사용자 또는 회사가 최대 사용률에 맞추어서 컴퓨터 장비를 구매하는 대신, 필요할 때에 필요한 만큼의 컴퓨팅 자원만 전문 회사한테서 대여해서 사용하는 방식이 클라우드 서비스 개념이다. 이러한 클라우드 서비스로서는 Amazon elastic cloud, salesforce.com, KT UCloud service 등이 있다. 이때에 컴퓨팅 자원을 사용자가 원하는 환경에 맞추어서 사용자의 유틸리티를 높이면서 분배(distribute)하는 문제가 연구되어 왔으며 이것이 클라우드 컴퓨팅 자원 배분(cloud computing resource allocation) 문제이다.

클라우딩 컴퓨팅 자원 배분에 관한 문제는 많이 연구되어왔다. 초기에는 단순히 사용자가 원하는 태스크(task)을 처리하도록 자원(resource)을 분배하는 경우만 고려했지만 시간이 지날수록 유틸리티(utility)에 대해 연구하기 시작했다. 여기서 태스크란 사용자가 수행하고자 하는 작업의 단위로서 여러 개의 더 작은 단위 태스크(subtask)로 구성되도록 모델링 할 수 있다. 사용자의 유틸리티를 높이는 문제는 시간과 비용에 대해 가중치를 두어 연구가 되어왔고 주로 하나의 자원이 하나의 단위 태스크만을 처리한다고 가정하고 문제를 해결했다.

클라우드 컴퓨팅 자원 배분과 관련된 문제를 다루는 기존의 연구는 다음과 같이 분류될 수 있다.

첫 번째로, 연구의 목적으로 시간이나 비용을 변수로 가지는 함수를 최소화하거나 최대화 하는 연구들이 있다. 클라우드 자원 배분(cloud resource allocation)으로 시간과 비용을 변수로 가지는 유틸리티의 최대화를 목표로 한다. 목표를 시간을 줄이거나 옵티멀(optimal)한 캐퍼시티(capacity) 근처에서 옵티멀한 가격을 만드는 것을 목표로 하였다. 비슷하게 가장 작은 가격을 만들어 유틸리티를 설정해 사용자의 이익을 최대화하였다.

두 번째로는 각 지역(area) 에서 수용 가능한 전력 용량(electric power capacity)가 제한된 상황에서 처리능력(processing ability)과 대역폭(bandwidth)을 최적화 시키는 것과 총 전력 소비(electric power consumption)를 최소화하는 것을 목표로 하였다. 다른 예를 들어, 단순하게 사용자의 요구를 가장 만족하게 하는 것을 목표로 설정하거나, 수요 탄성(demand elasticity)을 증가시키는 것을 목표로 한다.

세 번째로, 게임 이론(game theory)을 사용한 방법들이 있다. 게임이론으로서 Stackelberg game 과 Nash equilibrium을 사용했다.

마지막으로 배분에 다른 방법들을 사용한 연구들이 있다. 가상 머신(Virtual machine)을 기반으로 한 배분 외에도 second-priced auction mechanism을 사용하였다. Nash equilibrium 이외에 M/M/1 queuing system 와 NECDA 라는 휴리스틱 방법을 사용하였다. 가상 머신을 기반으로 한 것 외에 lightweight resource management model인 elastic application container 기반 배분을 하였다. 역시 가상 머신 외에 각각 Resource Over-Reservation(ROR)과 Vickrey-Clarke-Groves mechanism를 사용하였다.

또한, 공급자가 사용자에게 reservation plan 과 on-demand plan, 두 가지 배분 계획을 제공한다. 사용자에게 좋은 환경을 주려면 기기(application)의 속도가 빨라야 한다. 그 속도는 기기 구성요소(application component) 위치에 따라 달라져 구성요소 위치를 제공하는 방법을 제안한다. 그리고 distributed cloud에 대한 자원 배분 처리(resource allocation process) 및 모바일(mobile)에서의 클라우드 보안 서비스(cloud security service)를 주요하게 다룬다.

일 실시예에 따르면 IVSCD를 이용하여 자원을 배분할 수 있다.

일 실시예에 따르면 태스크의 크기와 상관 없이 자원을 배분할 수 있다.

일 실시예에 따르면 할당 매트릭스의 그래프로부터 사이클(cycle)을 삭제하여 자원을 배분할 수 있다.

일 실시예에 따르면 태스크의 조건에 맞지 않는 자원은 분배를 금지할 수 있다.

일 실시예에 따르면, 처리되어야 하는 태스크(task) 및 상기 태스크에 사용되는 자원에 대한 정보를 수집하는 자원 정보 수집부 및 상기 정보에 따라 IVSCD(Initial Value Setting and Cycle Deletion)를 이용하여 유틸리티가 증가되도록 상기 태스크를 상기 자원에 분배하는 자원 분배부를 포함하는 효율적인 자원 배분 장치가 제공될 수 있다.

다른 일 실시예에 따르면, 상기 자원 분배부는, 상기 정보에 따라 상기 자원 및 상기 태스크를 매핑한 초기 할당 매트릭스를 설정하고, 상기 초기 할당 매트릭스보다 유틸리티 총합이 증가된 최종 할당 매트릭스를 생성하며, 상기 최종 할당 매트릭스에 기초하여 상기 태스크를 상기 자원에 배분하는, 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면, 상기 자원 분배부는, 각 상기 태스크가 포함하는 단위 태스크 개수 순서로 상기 태스크를 정렬하여 초기 할당 매트릭스를 설정하는, 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면, 상기 자원 분배부는, 상기 자원을 공유하는 횟수가 최소화되도록 상기 초기 할당 매트릭스를 설정하는, 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면, 상기 자원 분배부는, 상기 자원이 공유되는 횟수에 기초하여 상기 태스크를 처리하는데 소요되는 실행시간을 유지하면서 상기 자원이 소모하는 비용을 최소화하는 상기 최종 할당 매트릭스를 생성하는, 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면, 상기 자원 분배부는, 상기 초기 할당 매트릭스의 원소를 연결하는 엣지로 된 그래프를 생성하고, 상기 그래프로부터 사이클 삭제(cycle deletion)를 수행하여 상기 최종 할당 매트릭스를 생성하는, 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면 상기 자원 분배부는, 상기 태스크에 따라 상기 엣지를 인접하지 않은 엣지와 다르게 컬러링(coloring)하는, 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면, 상기 자원에 대한 정보는, 상기 자원이 사용될 때 소모되는 단위시간당 필요한 비용을 포함하는 각 자원의 값 정보를 포함하는 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면, 상기 자원 분배부는, 상기 태스크의 조건에 맞지 않는 자원은 분배를 금지하는, 효율적인 자원 배분 장치가 제공될 수 있다.

또 다른 일 실시예에 따르면, 상기 유틸리티는, 상기 태스크를 처리하는데 소모되는 비용 및 실행시간을 최소화한 정도인, 효율적인 자원 배분 장치가 제공될 수 있다.

일 실시예에 따른 자원 배분 장치는 IVSCD에 따른 할당 매트릭스에 기초하여 자원을 효율적으로 배분할 수 있다.

일 실시예에 따른 자원 배분 장치는 자원이 공유되는 횟수를 최소화하여 실행시간을 유지하고, 할당 매트릭스의 그래프를 삭제하여 태스크를 완료하기 위해 자원이 소모하는 비용의 총합을 최소화할 수 있다.

일 실시예에 따른 자원 배분 장치는 IVSCD를 이용하여 사용자의 수 또는 자원의 개수가 증가할 수록 유틸리티의 총합을 향상시킬 수 있다.

도 1은 일 실시예에 따른 효율적인 자원 배분 장치의 개괄적인 구성을 도시한 도면이다.
도 2는 일 실시예에 따른 효율적인 자원 배분 장치의 세부적인 구성을 도시한 도면이다.
도 3은 일 실시예에 따른 일 실시예에 따른 효율적인 자원 배분 장치의 유틸리티 총합을 도시한 그래프이다.
도 4는 일 실시예에 따른 효율적인 자원 배분 장치의 자원에 따른 유틸리티 총합을 다른 방법과 비교한 그래프이다.
도 5는 일 실시예에 따른 효율적인 자원 배분 장치의 사용자 수에 따른 유틸리티 총합을 다른 방법과 비교한 그래프이다.
도 6은 일 실시예에 따른 효율적인 자원 배분 장치의 사용자와 자원 수에 따른 유틸리티 총합을 도시한 그래프이다.
도 7은 일 실시예에 따른 효율적인 자원 배분 장치의 사용자와 자원 수에 따른 유틸리티 총합을 3D로 도시한 그래프이다.
도 8은 Wei 방법의 사용자와 자원 수에 따른 유틸리티 총합을 3D로 도시한 그래프이다.

이하, 실시예들을 첨부된 도면을 참조하여 상세하게 설명한다.

도 1은 일 실시예에 따른 효율적인 자원 배분 장치(100)의 개괄적인 구성을 도시한 도면이다. 일 실시예에 따르면 자원 배분 장치(100)는 n명의 사용자(190)가 요청한 태스크(task)를 m개의 자원(180)에 효율적으로 분배할 수 있다. 예를 들어 클라우드 컴퓨팅을 효율적으로 수행하기 위해 m개의 자원(180)을 분배하는 경우, 각 자원(180)은 클라우드 네트워크 상으로 연결된 컴퓨터 및 기타 단말을 포함할 수 있다. 다만, 클라우드 시스템 분야에서의 자원 분배로 한정하는 것은 아니고, 일 실시예에 따른 특정 조건을 충족하는 일반적인 자원 분배 문제에서도 적용될 수 있다. 일 실시예에 따르면 자원 배분 장치(100)는 태스크의 크기와 상관 없이 자원을 배분할 수 있다

도 2는 일 실시예에 따른 효율적인 자원 배분 장치(200)의 세부적인 구성을 도시한 도면이다. 여기서 자원 배분 장치(200)는 자원 정보 수집부(210) 및 자원 분배부(220)를 포함할 수 있다.

자원 정보 수집부(210)는 처리되어야 하는 태스크 및 태스크에 사용되는 자원에 대한 정보를 수집할 수 있다. 여기서 태스크에 대한 정보는 태스크를 수행하기 위해 필요한 조건, 태스크의 종류 및 기타 태스크와 관련된 정보를 포함할 수 있고, 조건에 맞지 않는 자원에는 해당 태스크의 분배가 금지될 수 있다. 또한, 자원에 대한 정보는 자원을 단위 시간만큼 사용할 때 필요한 비용을 포함할 수 있다.

자원 분배부(220)는 자원 정보 수집부(210)에서 수집한 정보에 따라 IVSCD(Initial Value Setting and Cycle Deletion)를 이용하여 유틸리티가 증가되도록 n개의 태스크를 프로세서를 통해 m개의 자원에 분배할 수 있다. 여기서 n 및 m은 0보다 큰 정수일 수 있다.

일 실시예에 따르면 자원 분배부(220)는 프로세서를 통해 수집한 정보에 따라 자원 및 태스크를 매핑한 초기 할당 매트릭스를 설정하고, 초기 할당 매트릭스보다 유틸리티 총합이 증가된 최종 할당 매트릭스를 생성하며, 최종 할당 매트릭스에 기초하여 태스크를 자원에 배분할 수 있다.

여기서 초기 할당 매트릭스는 태스크가 포함하는 단위 태스크 개수 순서로 태스크를 정렬하고, 자원을 공유하는 횟수가 최소화되도록 초기 할당 매트릭스를 설정하여 설정될 수 있다.

그리고 최종 할당 매트릭스는 초기 할당 매트릭스의 실행시간을 유지하면서 자원이 소모하는 비용이 최소화되도록 생성될 수 있다. 예를 들면, 자원이 공유되는 횟수에 기초하여 태스크를 처리하는데 소요되는 실행시간을 유지할 수 있다. 구체적으로 자원 분배부(220)는 초기 할당 매트릭스의 구성요소를 나타내는 노드를 연결하는 엣지로 된 그래프를 생성하고, 당해 그래프에서 사이클을 검색하여, 검색된 사이클에 대해 사이클 삭제를 수행하여 최종 할당 매트릭스를 생성할 수 있다.

일 실시예에 따른 자원 배분 장치(200)의 자원 분배부(220)가 자원을 분배하는 구체적인 방법은 하기에서 상세히 설명한다.

클라우드 컴퓨팅 자원 배분(Cloud Computing Resource Allocation)은 사용자가 원하는 태스크를 클라우드 자원에 할당해서 처리하는 것을 의미할 수 있다. 여기서 사용자의 "유틸리티"를 높이는 것이 중요할 수 있다. 여기서 유틸리티는 태스크를 처리하는데 소모되는 비용 및 실행시간을 최소화한 정도로서 하기 수학식 8과 같이 나타낼 수 있다.

본 명세서에서는 이 문제를 위한 시스템 모델을 정립하고 "유틸리티"를 수식적으로 모델링 했으며, 자원 할당을 위한 ALLOC문제를 공식적으로 정의할 수 있다. ALLOC문제는 NP-hard 문제이므로 휴리스틱 해결책이 필요할 수 있다. ALLOC문제 및 이에 가능한 해법 할당 매트릭스(allocation matrix)를 분석한 결과로부터 도출된 사용자 유틸리티를 항상 향상시킬 수 있는 원칙을 기반으로 고안된 IVSCD(Initial Value Setting and Cycle Deletion) 알고리즘을 사용할 수 있다.

일 실시예에 따르면 하나의 자원이 하나의 단위 태스크만을 처리하는 것으로 제한할 필요는 없으며 여러 개의 단위 태스크를 처리하는 모델을 사용할 수 있다. 이에 따라 하나의 자원이 여러 개의 단위 태스크를 처리 가능하다고 보고 문제를 해결하면서 사용자의 유틸리티를 높일 수 있다. 기존 하나의 자원이 하나의 단위 태스크를 처리하던 방식을 여러 개의 단위 태스크를 처리 한다고 가정함으로써 문제를 확장시켜 일반화해 해결할 수 있다.

하기 시스템 모델을 기반으로 휴리스틱 방법인 IVSCD(Initial Value Setting and Cycle Deletion)알고리즘을 제안했으며 이 방법을 분석한 결과, 기존의 방법과 쉽게 생각해낼 수 있는 다른 휴리스틱 방법보다 사용자의 수가 50 이상 100 이하일 때 시뮬레이션으로 분석한 결과, IVSCD는 성능이 최소 46.58%, 평균 93.87% 향상될 수 있다. 다양한 사용자 수 n 및 자원의 개수 m에 대한 결과는 하기 도 3 내지 도 8에서 도시된 바와 같을 수 있다.

일 실시예에 따르면 임의의 방법 또는 랜덤(random)한 접근 방식 내지 이미 알려져 있는 알고리즘들을 통한 것이 아닌, 체계적인 접근을 통해 문제의 특성에 대한 하기 수학식 10 내지 수학식 14의 정리(theorem)들을 고안하여 만들어진 자원 배분 알고리즘 IVSCD를 사용할 수 있다. 시뮬레이션으로 검증한 결과 기존 방법에 비해 평균 93.87% 향상될 수 있다.

기존에는 각각의 자원들이 한 사용자가 요청한 하나의 단위 태스크만 처리할 수 있었으나, 일 실시예에 따르면 각각의 자원들이 여러 단위 태스크를 처리할 수 있다. 또한, 각각의 자원들이 사용자에 의해 금지될 확률이 발생할 수 있다. 여기서 사용자에 의해 금지될 확률은, 사용자가 요구하는 태스크를 각각의 자원들이 처리하지 못하는 확률을 포함할 수 있다.

일 실시예에 따르면 n개의 태스크들을 해결할 수 있도록 m개의 자원들을 적절히 배치할 수 있다. 이러한 배치를 통해 유틸리티를 극대화함으로써 실행 시간, 금전적인 비용 등이 적절하게 조합되어 효율성이 향상될 수 있다. 여기서 유틸리티가 향상되도록 n개의 태스크에 대한 m개의 자원을 배치하는 모델은 하기 수학식 1 내지 수학식 8과 같이 나타낼 수 있다.

상술한 수학식 1에서, R은 자원들의 집합, S는 태스크들의 집합을 나타낼 수 있고, 어떤 자원

을 단위시간만큼 사용할 때 필요한 비용은

로 나타낼 수 있다.

그리고 상술한 수학식 2와 같이

크기의 매트릭스 B를 나타낼 수 있다. 여기서 임의의 원소

에 대해

이면

를

에 할당할 수 있고,

이면

를

에 할당하지 못할 수 있다.

상술한 수학식 3에서 임의의 태스크

들은

개의 단위태스크로 이루어질 수 있다. 이를테면,

를 수행하기 위해서 우리는

개의 단위 태스크 모두를 해결해야 하며 각각의 단위 태스크가 요구하는 계산양은 동일할 수 있다.

상술한 수학식 4에서

크기의 매트릭스 A를 할당 매트릭스로 나타낼 수 있다. 할당 매트릭스 A에서 각 원소는

에게

의 단위 태스크를

개만큼 할당시킨 것을 의미할 수 있다. 여기서,

이고,

이 성립할 수 있다.

상술한 수학식 5에서 임의의 할당 매트릭스 A에 대해 같은 크기의 매트릭스 E를 비용(expense) 매트릭스로 나타낼 수 있다 여기서 원소

의 값은 태스크

를

로 해결하는데 필요한 비용을 나타낼 수 있다.

상술한 수학식 6에서 임의의 할당 매트릭스 A에 대해 같은 크기의 매트릭스 T를 실행시간 매트릭스(execution time matrix)로 나타낼 수 있다 원소

의 값은 태스크

를

로 해결하는데 걸리는 실행시간을 나타낼 수 있다.

상술한 수학식 7과 같이

크기의 매트릭스

를 나타낼 수 있다. 여기서,

의 원소

의 값은

의 단위 태스크 한 개를

로 해결하기 위해 걸리는 시간을 의미할 수 있다. 이를테면, 상기 수학식 5의 원소

및 수학식 6의 원소

와의 관계는

,

와 같이 나타낼 수 있다.

그리고 임의의 두 상수

와

는 일 실시예에 따라 자원이 태스크에 분배는 경우, 각각 비용과 실행시간에 대한 가중치를 나타낼 수 있다. 또한, 각 자원

에 대해 사용자가 요구하는 조건에 맞지 않을 확률을

로 나타낼 수 있다.

상술한 수학식 8은 사용자가 지출해야 하는 비용과 자신이 원하고자 하는 태스크를 마치기까지 걸리는 시간을 이용하여 i번째 사용자 내지 태스크가 얻을 수 있는 유틸리티

를 나타낼 수 있다. 여기서

가 여러 기계에 분산되었을 때 전체 실행 시간은 가장 느린 기계에 의해서 결정될 수 있다. 또한 전체 비용은 각 기계에서 요구하는 비용의 합으로 볼 수 있다. 일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분은 상술한 수학식 8에 따른 모델로 나타낼 수 있다.

구체적으로 각각의 태스크

는

개의 단위 태스크를 포함하고,

개의 단위 태스크는 사용 가능한 자원

에서

사이에 할당될 수 있으며, 최종 할당 결과는 할당 매트릭스 A 형태로 나타낼 수 있다. 이러한 ALLOC문제는 공식으로는 다음 수학식 9와 같이 나타낼 수 있다.

상술한 수학식 9에서 입력(input) 중 n은 사용자의 수, m은 자원의 수,

는 태스크,

는 각 태스크에 포함된 단위 태스크의 개수,

는 자원,

는 각 자원이 사용될 때 소모되는 단위시간당 필요한 비용을 포함하는 각 자원의 값 정보,

및

는 시간과 비용에 대한 가중치,

는 단위 태스크 하나를

로 수행하기 위해 소요되는 시간에 대한 매트릭스,

는 각 자원의 각 태스크에의 할당 가부를 나타내는 매트릭스,

는

자원이 금지될 확률을 나타낼 수 있다. 그리고 상술한 수학식 9에서 출력(output)으로 되는 할당 매트릭스 A의 각 원소는 상술한 수학식 4를 만족할 수 있다.

여기서 상술한 수학식 9에 대한 출력인 A는 복수 개 존재할 수 있으나, 여러 할당 매트릭스 A 중 A1과 A2를 비교하면 유틸리티의 합이 큰 매트릭스가 자원 배분을 보다 효율적으로 수행된 것일 수 있다. 따라서 상술한 수학식 9에 대한 출력 A1과 A2가 있을 때 A1의 유틸리티의 합이 A2의 유틸리티의 합보다 높으면 A1이 A2보다 더 좋은 해법일 수 있다.

일 실시예에 따른 ALLOC문제는 기존의 금지자원 및 한 자원에 여러 개의 단위 태스크를 할당할 수 있도록 변경한 것이다. 일 실시예에 따른 ALLOC문제는 금지자원을 사용하지 않고 단위 태스크 할당을 제한적으로 하면 NP-hard이므로 ALLOC문제도 NP-hard임이 증명될 수 있다. 따라서 ALLOC문제는 NP-hard하므로 자원 및 사용자가 많을 경우 휴리스틱 알고리즘을 사용할 수 있다.

일 실시예에 따른 IVSCD 알고리즘은 최적의 해를 찾는 대신 유틸리티의 합이 높은 더 좋은 해법을 찾는 알고리즘으로서, 알고리즘을 체계적으로 구현하기 위해 필요한 정리들은 아래 수학식들과 같이 나타낼 수 있다.

상술한 수학식 10에 대한 증명은 아래와 같이 나타낼 수 있다. 우선,

의 실행시간 매트릭스 는 다음과 같이 나타낼 수 있다.

상술한 실행시간 매트릭스에 비용을 곱한 비용(expense) 매트릭스는 다음과 같이 나타낼 수 있다.

상술한 비용 매트릭스를

라고 나타내면 상술한 수학식 8에 의해 각 자원의 유틸리티 값은 다음과 같이 나타낼 수 있다.

다음으로

의 경우에 대한 실행시간 매트릭스는 다음과 같이 나타낼 수 있다.

여기서 상술한 실행시간 매트릭스에 대해 수학식 5에 따른 비용 매트릭스는 다음과 같이 계산되어 나타낼 수 있다.

이러한 비용 매트릭스를 상술한

로 표현하면

로 나타낼 수 있고, 이 때의 유틸리티

은 다음과 같이 나타낼 수 있다.

다른 할당 매트릭스인

의 비용 매트릭스는

이므로 당해 매트릭스에 대한 유틸리티

는 다음과 같이 나타낼 수 있다.

상술한 유틸리티들 중 제1 사용자에 대한 유틸리티는 다음과 같이 표현될 수 있다.

여기서 제1 사용자에 대한 각 유틸리티는

과 같이 나타낼 수 있고, 산술 기하 부등식,을 통해 다음과 같은 관계가 성립될 수 있다.

따라서

도 성립할 수 있는 바, 제1 사용자 및 제2 사용자에 대한 두 식을 합하면

과 같은 관계가 도출될 수 있다. 이를테면

와

중 하나는

이상일 수 있다.

결과적으로

와

, 둘 중 하나는

보다 유틸리티가 더 높을 수 있다.

상술한 수학식 11의 정리를 증명하기 위해 할당 매트릭스 A는 다음과 같이 설정될 수 있다.

를 포함하는 두 행에서

를 제외한 나머지 태스크들의 비용의 합과 최대 시간을 각각

로 나타낼 수 있다. 그리고

가 있는 열은

를 포함한 태스크의 개수를 x개라고 가정하고,

가 있는 열은

를 포함하여 태스크의 개수를 y개라고 다음과 같이 가정할 수 있다.

여기서 상술한 실행시간 매트릭스는 다음과 같이 나타낼 수 있다.

상술한 수학식 10에서 나타난 방법과 유사하게 상술한 실행시간 매트릭스를 비용 매트릭스로 다음과 같이 바꿔서 나타낼 수 있다.

이어서 수학식 10을 증명한 과정과 유사하게

로 다음과 같이 나타낼 수 있다.

상술한 a, b, c, d로 치환된 매트릭스로부터 각 사용자에 대한 유틸리티는 다음과 같이 나타낼 수 있다.

그리고 수학식 10과 유사하게

부분을

,

로 대체할 수 있다. 예를 들어,

에 대한 비용 매트릭스는 다음과 같이 나타낼 수 있다.

이러한 비용 매트릭스를

로 다음과 같이 다시 표현할 수 있다.

각 사용자에 대한 유틸리티를

은 다음과 같이 나타낼 수 있다.

다른 예를 들어,

의 유틸리티는 다음과 같이 나타낼 수 있다.

여기서,

,

라 하면, 상술한 수학식 10으로부터

가 성립할 수 있다. 따라서

이므로 두 식을 더하면

가 성립할 수 있다. 이를테면,

또는

중 하나 이상은

이상일 수 있다. 그리고

를 제외한

나머지할당 매트릭스의 원소는 유틸리티의 변화가 없으므로 최종적으로

를 포함한 매트릭스보다

혹은

로 치환한 매트릭스의 유틸리티의 합이 더 증가할 수 있다.

상술한 수학식 12의 정리를 증명하기 위해서,

의 i번째 열의 단위 태스크 개수의 합을

라고 표현할 수 있다. 또한 다음과 같이

를 포함한 각 행에서

를 제외한 나머지 태스크들의 비용 합과 최대 시간을 각각

,

으로 나타낼 수 있다.

우선 상술한 수학식 10 및 수학식 11과 유사하게 실행시간 매트릭스를 다음과 같이 나타낼 수 있다.

여기서 상술한 실행시간 매트릭스에 대한 비용 매트릭스는 다음과 같이 나타낼 수 있다.

이로부터 각 사용자에 대한 유틸리티

는 다음과 같이 계산될 수 있다. 다만, i가 n일 때는 i+1을 1로 계산할 수 있다.

예를 들어,

에 대한 실행시간 매트릭스는,

이고, 당해 실행시간 매트릭스에 대한 비용 매트릭스는 다음과 같이 나타낼 수 있다.

여기서 유틸리티

는 다음과 같이 나타낼 수 있다.

다른 예를 들어,

에 대한 유틸리티

는 다음과 같이 나타낼 수 있다.

이 때,

,

라고 하면,

가 되고

가 성립할 수 있다. 이로부터

또는

가

보다 높을 수 있으므로,

둘 중 하나가

보다 더 좋은 매트릭스일 수 있다.

상술한 수학식 13을 증명하기 위해 할당 매트릭스 A를 다음과 같이 설정할 수 있다.

여기서 각각의 행을

이라고 할 수 있는 바, 매트릭스 A에서 행을 바꿔 주어도 사용자의 수, 자원의 수, 사용자들의 요구는 변함이 없기 때문에 행이 바뀌어도 무방할 수 있다. 이를테면,

의 순서가 아닌

과 같이 임의의 순서로 재배열해도 무방할 수 있다. 만약 매트릭스 A가

를 만족하는

이 존재한다면 A의 행들을 바꿔주어 상술한 수학식 12와 같은 모양의 매트릭스로 만들 수 있다. 따라서 매트릭스 A 는 수학식 12의 매트릭스와 동치가 되므로 수학식 12에 대해 상술한 증명을 통해 수학식 13 또한 증명될 수 있다.

상술한 수학식 14에서 필요충분조건임을 증명하기 위해 필요조건임과 충분조건임을 다음과 같이 증명할 수 있다.

우선, 필요조건을 증명하기 위해

를 만족하는

가 존재한다고 가정할 수 있다. 예를 들어, 임의의 i에 대해

이므로 G에서

에서

로 가는 길이 존재하는데,

이므로

에서

로 가는 길이 존재할 수 있다. 결과적으로

사이클(cycle)이 그래프 G에 존재할 수 있다. 여기서 사이클은 매트릭스의 원소를 노드로 하여 각 노드를 엣지로 연결한 그래프 상에 나타나는 폐곡선으로 된 도형을 의미할 수 있다.

다음으로 충분조건을 증명하기 위해 그래프 G에 사이클 C가 존재한다고 가정할 수 있다. C는 노드가

인 사이클일 수 있다.

의 엣지(edge)를

라고 나타낼 수 있다. 이를테면 사이클 C는

로 표현될 수 있고, 여기서 인접하지 않은 엣지들은 마크된 컬러(color)가 다를 수 있다. 구체적으로는 인접하지 않은 엣지

,

의 컬러링(coloring)이 c로 같다면, 사이클에 노드 Rc가 두 번 이상 출현하게 되므로 가정에 모순될 수 있다.

이어서, 사이클 C로부터

를 만족하는

를 생성할 수 있다. 이 때 생성하는 방법은

에 대해

이라면 시퀀스 b에

를, 시퀀스 c에

를 추가할 수 있다. 이렇게 생성된 시퀀스 b, c는

를 만족할 수 있다. 따라서 두 개의 조건이 필요충분임이 증명될 수 있다.

일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치는 상술한 수학식 1 내지 수학식 14에 따른 시스템 모델 및 분석을 기반으로 하는 휴리스틱 알고리즘인 IVSCD를 사용할 수 있다. 여기서 IVSCD 알고리즘은 init_alloc 및 cycle deletion 두 파트로 구성될 수 있다.

우선, init_alloc은 초기 할당 매트릭스를 설정할 수 있다. 수학식 8로부터 실행시간은

에 의존될 수 있으므로 ALLOC문제의 가능한 솔루션인 최종 할당 매트릭스

는 실행시간이 고루 분배된 형태일 수 있다. 하지만 실행시간이 균등해지기에 앞서, 자원들이 공유되는 횟수가 최소화될 수 있다. 여기서 공유 횟수는 자원들에 할당되는 단위 태스크의 개수일 수 있다.

여기서 초기 할당 매트릭스

는 다음과 같이 설정될 수 있다. 1)

이 되도록 정렬하고, 2) 각

에 대해서, 각

에 대해 현재 공유된 횟수를

라 하면

가 작은 순서대로

를 채우되, H값이 같고

이라면

를,

이면

를 먼저 채울 수 있다. 또한,

를 채울 때마다

를 갱신할 수 있다. 이런 과정은 다음 표 1과 같은 pseudocode로 표현될 수 있다.

Def init_alloc:

그리고 Cycle deletion에서 사이클 삭제가 수행될 수 있다. init_alloc에서 완성된 초기 할당 매트릭스

에서는 비용에 대해 전혀 고려되지 않을 수 있다. 실행시간에 대한 부분은 init_alloc에서 최소화된 바,

의 실행시간을 늘리지 않는 조건에서 비용을 줄이는 사이클 삭제를 시행할 수 있다.

구체적으로

의 실행시간을 늘리지 않으며 비용을 최대한 줄인 최종 할당 매트릭스

는 다음과 같이 생성될 수 있다. 1) 그래프를 초기화하고, 2) 모든

에 대해 A의 i번째 행에서 0이 아닌 수가 가장 처음 등장하는 위치를 찾아

에 저장할 수 있다. 그리고 3) 모든

에 대해, 엣지에

를 추가한 후 노드={1, ..., m}으로 설정할 수 있으며, 4) 사이클을 찾고 없다면 Cycle deletion의 9) 과정을 수행할 수 있다. 5) 사이클을 찾은 경우 찾은 사이클의 노드에 대한 수열을 V, 엣지에 대한 수열을 E로 나타낼 수 잇다. 6)

를 만족하는 모든

에 대해, RED 에 점

, BLUE에 점

를 추가할 수 있다. 이어서, 7)

는

,

을 할당할 수 있고, 8) A<A'면, A를 A'으로 한 뒤 Cycle deletion의 1), A>A'면, Aij=...한 뒤 Cycle deletion의 1)을 다시 수행할 수 있다. 마지막으로 9) A 리턴할 수 있다. 이러한 Cycle deletion에 대한 pseudocode는 다음 표 2와 같이 나타낼 수 있다.

Def cycle_deletion:

상술한 pseudo code로부터 일 실시예에 따른 IVSCD 에서 while 문이 총

번 실행되고 한 번 실행될 때마다 for 문이

번씩 실행되므로 time complexity는

일 수 있다.

일 실시예에 따른 IVSCD를 평가하기 위한 시뮬레이션은 결과를 얻기 위해 C++을 이용해 코딩하여 구현된 것으로서, 사용자의 수(n)는 100, 200, 300,..., 1000 중 임의로 선택될 수 있고, 자원의 수(m)는 10, 20, 30, ..., 100중 임의로 선택될 수 있다.

일 실시예에 따르면 실행시간 매트릭스 T의 원소들은 2이상 20이하인 유리수로, 비용 매트릭스 E의 원소들은 1이상 10이하인 유리수로 설정할 수 있다. 그리고 자원의 금지 개수는 0개 이상 (m-1)개 이하로 설정할 수 있고, 각 자원이 금지 될 확률은 {0, 0.2, 0.8} 중 하나로 설정될 수 있다. 여기서 IVSCD 알고리즘으로 도출된 유틸리티가 최대가 되는 매트릭스를 종래의 Wei 알고리즘, Greedy 알고리즘을 비교한 것일 수 있다. 아래 그래프들은 IVSCD와 다른 알고리즘과의 비교 결과를 보여줄 수 있다.

도 3은 일 실시예에 따른 일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치의 유틸리티 총합을 도시한 그래프이다. 구체적으로는 사용자의 수가 1000명, 자원의 개수가 100개일 때에 대한 각 사용자들의 유틸리티의 합을 나타낸 그래프일 수 있다.

여기서 IVSCD 알고리즘이 Wei 방법보다 평균 122.07% 최대 136.87% 최소 106.56% 향상된 유틸리티 결과, Greedy 방법보다는 평균 310.14% 최대 332.85% 최소 287.22% 향상된 결과가 나타날 수 있다.

도 4는 일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치의 자원에 따른 유틸리티 총합을 다른 방법과 비교한 그래프이다. 구체적으로는 사용자의 수를 1000명으로 고정 시켰을 때 자원의 개수에 따른 유틸리티의 합을 나타낸 그래프일 수 있다.

여기서 IVSCD 알고리즘이 Wei 방법보다 평균 100.46% 최대 122.07% 최소 46.58% 향상된 유틸리티 결과, Greedy 방법보다는 평균 229.39% 최대 310.14% 최소 82.59% 향상된 결과가 나타날 수 있다.

도 5는 일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치의 사용자 수에 따른 유틸리티 총합을 다른 방법과 비교한 그래프이다. 구체적으로는 자원의 수를 100개로 고정 시켰을 때 사용자의 수에 따른 유틸리티의 합을 나타낸 그래프일 수 있다.

여기서 IVSCD 알고리즘이 Wei 방법보다 평균 91.37% 최대 122.07% 최소 28.77% 향상된 유틸리티 결과, Greedy 방법보다는 평균 282.89% 최대 310.14% 최소 213.20% 향상된 결과가 나타날 수 있다.

도 6은 일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치의 사용자와 자원 수에 따른 유틸리티 총합을 도시한 그래프이다. 구체적으로는 IVSCD의 알고리즘만을 나타낸 그래프일 수 있다.

여기서 도 6에 도시된 그래프는 자원의 개수가 10개부터 100개까지 변화되고, 사용자의 수가 100, 500, 1000명인 경우에 관한 시뮬레이션 결과를 나타내는 것일 수 있다. 이러한 시뮬레이션 결과에 따르면 IVSCD 방법은 자원의 수가 많을수록, 사용자의 수가 많을수록 유틸리티가 향상하는 정도가 증가할 수 있다.

도 7은 일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치의 사용자와 자원 수에 따른 유틸리티 총합을 3D로 도시한 그래프이다. 도 8은 Wei 방법의 사용자와 자원 수에 따른 유틸리티 총합을 3D로 도시한 그래프이다. 구체적으로 도 7 및 도 8은 자원의 개수를 10개에서 100개, 사용자의 수를 100명에서 1000명까지 변화시켰을 때의 유틸리티를 연속적으로 나타낸 그래프일 수 있다.

여기서 일 실시예에 따른 IVSCD에 대한 시뮬레이션 결과를 나타내는 도 7은 그래프가 사용자의 수와 자원의 개수가 늘어날수록 유틸리티가 높아져서 위로 볼록한 모양으로 나타날 수 있으나, 종래의 Wei에 대한 시뮬레이션 결과를 나타내는 도 8 는 사용자의 수와 자원의 개수에 상관없이 평평한 모양을 나타낼 수 있다. 이러한 시뮬레이션 결과에 따르면 IVSCD 알고리즘은 사용자의 수 또는 자원의 개수가 증가할 수록 다른 알고리즘보다 보다 자원 배분의 효율을 향상시킬 수 있다.

일 실시예에 따른 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치는 자원을 필요로 하는 사용자에게 효율적으로 배분하여 사용자의 유틸리티를 높이는 IVSCD를 사용할 수 있다. 실행시간이 최대인 자원에 대한 태스크를 다른 자원에 배분하는 종래 알고리즘과는 차별화되는 IVSCD 알고리즘에서는 할당 매트릭스를 그래프로 바꾸어서 사이클을 삭제할 수 있다.

일 실시예에 따르면 클라우드 컴퓨팅을 위한 효율적인 자원 배분 장치에서 사용되는 IVSCD는 ALLOC문제를 위한 기존 휴리스틱에 의한 방법보다 사용자의 수가 50 이상 100 이하 일 때 최소 46.58%, 평균 93.87%의 향상이 시뮬레이션으로 나타날 수 있다.

이상에서 설명된 장치는 하드웨어 구성요소, 소프트웨어 구성요소, 및/또는 하드웨어 구성요소 및 소프트웨어 구성요소의 조합으로 구현될 수 있다. 예를 들어, 실시예들에서 설명된 장치 및 구성요소는, 예를 들어, 프로세서, 콘트롤러, ALU(arithmetic logic unit), 디지털 신호 프로세서(digital signal processor), 마이크로컴퓨터, FPA(field programmable array), PLU(programmable logic unit), 마이크로프로세서, 또는 명령(instruction)을 실행하고 응답할 수 있는 다른 어떠한 장치와 같이, 하나 이상의 범용 컴퓨터 또는 특수 목적 컴퓨터를 이용하여 구현될 수 있다. 처리 장치는 운영 체제(OS) 및 운영 체제 상에서 수행되는 하나 이상의 소프트웨어 애플리케이션을 수행할 수 있다. 또한, 처리 장치는 소프트웨어의 실행에 응답하여, 데이터를 접근, 저장, 조작, 처리 및 생성할 수도 있다. 이해의 편의를 위하여, 처리 장치는 하나가 사용되는 것으로 설명된 경우도 있지만, 해당 기술분야에서 통상의 지식을 가진 자는, 처리 장치가 복수 개의 처리 요소(processing element) 및/또는 복수 유형의 처리 요소를 포함할 수 있음을 알 수 있다. 예를 들어, 처리 장치는 복수 개의 프로세서 또는 하나의 프로세서 및 하나의 콘트롤러를 포함할 수 있다. 또한, 병렬 프로세서(parallel processor)와 같은, 다른 처리 구성(processing configuration)도 가능하다.

소프트웨어는 컴퓨터 프로그램(computer program), 코드(code), 명령(instruction), 또는 이들 중 하나 이상의 조합을 포함할 수 있으며, 원하는 대로 동작하도록 처리 장치를 구성하거나 독립적으로 또는 결합적으로(collectively) 처리 장치를 명령할 수 있다. 소프트웨어 및/또는 데이터는, 처리 장치에 의하여 해석되거나 처리 장치에 명령 또는 데이터를 제공하기 위하여, 어떤 유형의 기계, 구성요소(component), 물리적 장치, 가상 장치(virtual equipment), 컴퓨터 저장 매체 또는 장치, 또는 전송되는 신호 파(signal wave)에 영구적으로, 또는 일시적으로 구체화(embody)될 수 있다. 소프트웨어는 네트워크로 연결된 컴퓨터 시스템 상에 분산되어서, 분산된 방법으로 저장되거나 실행될 수도 있다. 소프트웨어 및 데이터는 하나 이상의 컴퓨터 판독 가능 기록 매체에 저장될 수 있다.

실시예에 따른 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 매체에 기록되는 프로그램 명령은 실시예를 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 상기된 하드웨어 장치는 실시예의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.

이상과 같이 실시예들이 비록 한정된 실시예와 도면에 의해 설명되었으나, 해당 기술분야에서 통상의 지식을 가진 자라면 상기의 기재로부터 다양한 수정 및 변형이 가능하다. 예를 들어, 설명된 기술들이 설명된 방법과 다른 순서로 수행되거나, 및/또는 설명된 시스템, 구조, 장치, 회로 등의 구성요소들이 설명된 방법과 다른 형태로 결합 또는 조합되거나, 다른 구성요소 또는 균등물에 의하여 대치되거나 치환되더라도 적절한 결과가 달성될 수 있다.

그러므로, 다른 구현들, 다른 실시예들 및 특허청구범위와 균등한 것들도 후술하는 특허청구범위의 범위에 속한다.

100: 자원 배분 장치
180: 자원
190: 사용자

Claims

처리되어야 하는 태스크(task) 및 상기 태스크에 사용되는 자원에 대한 정보를 수집하는 자원 정보 수집부; 및
상기 정보에 따라 IVSCD(Initial Value Setting and Cycle Deletion)를 이용하여 유틸리티가 증가되도록 상기 태스크를 상기 자원에 분배하는 자원 분배부
를 포함하는 효율적인 자원 배분 장치.
제1항에 있어서,
상기 자원 분배부는,
상기 정보에 따라 상기 자원 및 상기 태스크를 매핑한 초기 할당 매트릭스를 설정하고,
상기 초기 할당 매트릭스보다 유틸리티 총합이 증가된 최종 할당 매트릭스를 생성하며,
상기 최종 할당 매트릭스에 기초하여 상기 태스크를 상기 자원에 배분하는,
효율적인 자원 배분 장치.
제2항에 있어서,
상기 자원 분배부는,
각 상기 태스크가 포함하는 단위 태스크 개수 순서로 상기 태스크를 정렬하여 초기 할당 매트릭스를 설정하는,
효율적인 자원 배분 장치.
제2항에 있어서,
상기 자원 분배부는,
상기 자원을 공유하는 횟수가 최소화되도록 상기 초기 할당 매트릭스를 설정하는,
효율적인 자원 배분 장치.
제4항에 있어서,
상기 자원 분배부는,
상기 자원이 공유되는 횟수에 기초하여 상기 태스크를 처리하는데 소요되는 실행시간을 유지하면서 상기 자원이 소모하는 비용을 최소화하는 상기 최종 할당 매트릭스를 생성하는,
효율적인 자원 배분 장치.
제2항에 있어서,
상기 자원 분배부는,
상기 초기 할당 매트릭스의 원소를 연결하는 엣지로 된 그래프를 생성하고,
상기 그래프로부터 사이클 삭제(cycle deletion)를 수행하여 상기 최종 할당 매트릭스를 생성하는,
효율적인 자원 배분 장치.
제6항에 있어서,
상기 자원 분배부는,
상기 태스크에 따라 상기 엣지를 인접하지 않은 엣지와 다르게 컬러링(coloring)하는,
효율적인 자원 배분 장치.
제1항에 있어서,
상기 자원에 대한 정보는,
상기 자원이 사용될 때 소모되는 단위시간당 필요한 비용을 포함하는 각 자원의 값 정보
를 포함하는 효율적인 자원 배분 장치.
제1항에 있어서,
상기 자원 분배부는,
상기 태스크의 조건에 맞지 않는 자원은 분배를 금지하는,
효율적인 자원 배분 장치.
제1항 내지 제9항 중 어느 한 항에 있어서,
상기 유틸리티는,
상기 태스크를 처리하는데 소모되는 비용 및 실행시간을 최소화한 정도인,
효율적인 자원 배분 장치.