Load Balancing 이라는 개념은 앞으로 몇번 접하게 될 개념입니다. 컴퓨터분야에서뿐만 아니라 다른 분야 (예를 든다면 이삿짐 업체나, 택배업체, 우체국 등등..) 에서도 쓰입니다. Load Balancing은 역할분담을 가장 적당하고 고르게 하여 각각의 개체들이 부담을 적게 느끼고 전체 작업시간을 단축시킬수 있도록 해 줍니다. 간단한 LoadBalancingProblem 문제를 접하여보고 기회가 닿는다면 조금더 복잡한 종류의 문제를 풀어보는것도 좋을것 같습니다.
----
----
Problem name : Load Balancing ¶
SuperComputer 사는 N 개의 CPU 로 이루어진 슈퍼컴퓨터를 제작하였다. 각각의 CPU는 1에서 N 까지 번호가 새겨져 있으며 각각 독립적인 작업을 수행한다. 새로운 작업이 생기면 무작위로 한개의 CPU 에 그 작업이 할당된다. 이럴 경우 어떤 CPU 에는 작업이 엄청 많고 다른 CPU 에는 할당된 작업이 적거나 아예 없는 상황이 발생하게 된다. 이럴경우 각 CPU 에 작업을 적당하게 분배하여야 하는데 각각의 재분배 작업은 N번 CPU가 1-N, 1-N CPU 에 각각 하나씩의 작업을 전달하는 것이다. 차근차근 살펴보면,
- 1번 CPU의 작업의수를 본다. 다른 CPU 에 비해 작업이 많으면 양옆의 CPU 중에 한곳으로한 작업을 전달해줄수 있는데 1번 CPU 의 왼쪽에는 CPU 가 없으므로 2번 CPU 에만 작업을 전달해 줄 수 있다.
- 2번 CPU 의 작업의 수를 본다. 만약 2 번 CPU 의 작업의 수가 많다고 생각되면 1번, 3번 CPU 로 작업을 전달 해 줄수 있다.
- (...) N 번 CPU 를 본다. 작업을 전달해줘야 할 경우 N 번 CPU 의 오른쪽에는 CPU 가 없으므로, 왼쪽으로만 전달할 수 있다.
- 다시 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
출력값 ¶
- 작업의 이동 후 각각의 CPU 에 적당하게 작업이 분배되었는가?
- 작업의 이동 횟수는 얼마인가?
- 몇번 돌아보았는가? (1부터 N 까지 보았을때를 1 round 라고 한다)
source ¶
| 해결자 | 개발시간 | 사용언어 | Source |
| 강양욱 | . | Java |  IPSCLoadBalancing-macare.zip |
| 임인택 | . | Java | LoadBalancingProblem/임인택 (그냥 예전에 풀어놨던 것) |
| 나휘동 | . | Python | LoadBalancingProblem/Leonardong |
이 문제에 대한 의견이나 질문을 말해주세요 ¶
IPSC 라고 해서 엄청 어려운 문제도, 그렇다고 한번에 풀수 있는 쉬운 문제도 아닙니다. 풀어본 문제 몇개 중에서 재미있다고 생각되는 문제들을 여러 사람들이 함께 풀어보았으면 하는 바람에서 페이지를 열어보았습니다. - 임인택
----
see also IpscLoadBalancing, 문제은행
----
문제분류
