E D R , A S I H C RSS
ZeroWiki

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 2021-02-07 05:23:39
Processing time 0.0178 sec