E D R , A S I H C RSS

Load Balancing Problem

Load Balancing 이라는 개념은 앞으로 몇번 접하게 될 개념입니다. 컴퓨터분야에서뿐만 아니라 다른 분야 (예를 든다면 이삿짐 업체나, 택배업체, 우체국 등등..) 에서도 쓰입니다. Load Balancing은 역할분담을 가장 적당하고 고르게 하여 각각의 개체들이 부담을 적게 느끼고 전체 작업시간을 단축시킬수 있도록 해 줍니다. 간단한 LoadBalancingProblem 문제를 접하여보고 기회가 닿는다면 조금더 복잡한 종류의 문제를 풀어보는것도 좋을것 같습니다.
----

출제자

IPSC, 임인택이 한글화하고 요구하는 입&출력 스펙을 변경함

Problem name : Load Balancing

SuperComputer 사는 N 개의 CPU 로 이루어진 슈퍼컴퓨터를 제작하였다. 각각의 CPU는 1에서 N 까지 번호가 새겨져 있으며 각각 독립적인 작업을 수행한다. 새로운 작업이 생기면 무작위로 한개의 CPU 에 그 작업이 할당된다. 이럴 경우 어떤 CPU 에는 작업이 엄청 많고 다른 CPU 에는 할당된 작업이 적거나 아예 없는 상황이 발생하게 된다. 이럴경우 각 CPU 에 작업을 적당하게 분배하여야 하는데 각각의 재분배 작업은 N번 CPU가 1-N, 1-N CPU 에 각각 하나씩의 작업을 전달하는 것이다. 차근차근 살펴보면,

  1. 1번 CPU의 작업의수를 본다. 다른 CPU 에 비해 작업이 많으면 양옆의 CPU 중에 한곳으로한 작업을 전달해줄수 있는데 1번 CPU 의 왼쪽에는 CPU 가 없으므로 2번 CPU 에만 작업을 전달해 줄 수 있다.
  2. 2번 CPU 의 작업의 수를 본다. 만약 2 번 CPU 의 작업의 수가 많다고 생각되면 1번, 3번 CPU 로 작업을 전달 해 줄수 있다.
  3. (...) N 번 CPU 를 본다. 작업을 전달해줘야 할 경우 N 번 CPU 의 오른쪽에는 CPU 가 없으므로, 왼쪽으로만 전달할 수 있다.
  4. 다시 1 번 CPU 를 본다.
    .....
    (이 과정을 모든 CPU 가 최고-최저<=1 이 될때까지 반복한다)
    .....

입력값

IPSC 에는 입력을 파일로 받도록 하였으나 여기서는 직접 사용자가 다음과 같은 형식으로 입력한다.
~cpp 
CPU 의 갯수
초기에 각 CPU 에 할당된 작업의 수..
 
예를 들어보면,
~cpp 
3
0 99 3

8
16 17 15 0 20 1 1 2

10
0 0 100 0 0 0 0 0 0 0
 

출력값

  1. 작업의 이동 후 각각의 CPU 에 적당하게 작업이 분배되었는가?
  2. 작업의 이동 횟수는 얼마인가?
  3. 몇번 돌아보았는가? (1부터 N 까지 보았을때를 1 round 라고 한다)

source

해결자 개발시간 사용언어 Source
강양욱 . Java Upload:IPSCLoadBalancing-macare.zip
임인택 . Java LoadBalancingProblem/임인택 (그냥 예전에 풀어놨던 것)
나휘동 . Python LoadBalancingProblem/Leonardong

이 문제에 대한 의견이나 질문을 말해주세요

IPSC 라고 해서 엄청 어려운 문제도, 그렇다고 한번에 풀수 있는 쉬운 문제도 아닙니다. 풀어본 문제 몇개 중에서 재미있다고 생각되는 문제들을 여러 사람들이 함께 풀어보았으면 하는 바람에서 페이지를 열어보았습니다. - 임인택
----
see also IpscLoadBalancing, 문제은행
----
문제분류
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.2966 sec