Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Load Balancing Psudeocode
New Posts  All Forums:Forum Nav:

Load Balancing Psudeocode

post #1 of 9
Thread Starter 
Hi, need some help with some coding logic for a project....

Here are the paramaters:
* At any given time, there 0 to 40 processors
* At any given time, there are four thread types A, B, C, D to process.
* All processors should distribute the work as evenly as possible. However, it is more important to make sure all processors are in use.
* Each thread takes an unknown time to complete so polling is done for the number of idle processor. I also check the active processors and their current thread.

I have a few ideas on implementation but what do you have?
Edited by DuckieHo - 6/10/10 at 7:43pm
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
post #2 of 9
I'd just make a queue to hold the threads. If a thread is available dispatch to it, if not block until one becomes available. If you need to decide which to dispatch to in a fancier way than whatever's available, use a priority queue. The priority could be the %idle time over some rolling time window, or the thread's lifetime, or whatever.

Whatever language you're using likely has some sort of ThreadPool class in it's standard library. Check it out - it will probably suffice
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
post #3 of 9
Thread Starter 
Quote:
Originally Posted by rabidgnome229 View Post
I'd just make a queue to hold the threads. If a thread is available dispatch to it, if not block until one becomes available. If you need to decide which to dispatch to in a fancier way than whatever's available, use a priority queue. The priority could be the %idle time over some rolling time window, or the thread's lifetime, or whatever.

Whatever language you're using likely has some sort of ThreadPool class in it's standard library. Check it out - it will probably suffice
Can't.... they are aren't actually threads. I used the term to keep it simple.

If you want to know....
threads => configuration files
processors => model instances


My process isn't to create this configuration files. The model instances poll for these files. My load balancing process needs to assign instance number to the config file and the polling model will process it. In addition, the queue won't work because my process must be able to recover from server shutdowns and runaway threads. I already have to logic to cover that. I just need to tackle the load balancing now.
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
post #4 of 9
Couldn't you just poll each processor for the least number of threads in use when deciding where to send?

You could also have processors immediately request and receive new jobs when old ones complete; some kind of async messaging. I haven't quite thought it out too well, but it seems this may ensure even distribution, assuming an even distribution to begin with.
Callisto
(13 items)
 
  
CPUMotherboardGraphicsRAM
2500K 4.7ghz @ 1.37v MSI P67A-GD65 EVGA GTX 680 Mushkin Enhanced Redline 8GB (2 x 4GB) DDR3 1866 
Hard DriveOSMonitorPower
Intel SSD 40GB; Seagate Cavier Green 1TB Scientific Linux 6.3/Windoze7 22" Samsung SyncMaster 2232BW Corsair TX850 
  hide details  
Reply
Callisto
(13 items)
 
  
CPUMotherboardGraphicsRAM
2500K 4.7ghz @ 1.37v MSI P67A-GD65 EVGA GTX 680 Mushkin Enhanced Redline 8GB (2 x 4GB) DDR3 1866 
Hard DriveOSMonitorPower
Intel SSD 40GB; Seagate Cavier Green 1TB Scientific Linux 6.3/Windoze7 22" Samsung SyncMaster 2232BW Corsair TX850 
  hide details  
Reply
post #5 of 9
Thread Starter 
Quote:
Originally Posted by dharmaBum View Post
Couldn't you just poll each processor for the least number of threads in use when deciding where to send?

You could also have processors immediately request and receive new jobs when old ones complete; some kind of async messaging. I haven't quite thought it out too well, but it seems this may ensure even distribution, assuming an even distribution to begin with.
Read above.


Basically.... process starts and see there are 24 instances available and all 24 are idle. User submits a request that creates 140 config files of type A. Since there are 24 idle processes, the load balancer assigns the first 24 out 140 configs to the models. The load balancer checks the instances again a minute later and sees 18 working and 6 idle instances so it gives the next 6 configs for processing. Then user B submits a request of 10 config file of type B. Now, the load balancer should try to give 50/50 instances. So the next time there is an idle instance, the load balance assigns config of type B. If later another user submits 100 type C.... it should split the instances by 34/33/33. Load balancer polls again and see 20 instances working on A, 10 working on B, and 5 idle. It should give C to the 5 idle.

Yes, it is annoying but I can't control the model instances or design since I do not have multiple PhDs in mathematics.
Edited by DuckieHo - 6/10/10 at 7:56pm
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
post #6 of 9
I didn't really understand your clarification, so I'm going to pretend it's threads.

Keep a count of how many jobs are active on each thread. Every time you get a request, split them up to balance.

Pre request job numbers
[24 50 33 66] = 173 total

Request for 200 comes in = 373 total = 93 per thread
Additional jobs assigned
[70 43 60 27] = 200 total

New totals

[94 93 93 93] = 373 total
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
Reply
post #7 of 9
So, if I understand you correctly, each user submission should be evenly distributed between processors?

You could try a pre-processing of each submission, to determine the most efficient - or most balancing - distribution among the currently running processes. This would involve polling for the most available processors and determining where they should go before-hand. That is, scan the whole input to begin with and then, in the code, try to determine the best places for them to be sent. Attach this information to the config file and send it off to a meta-thread for delivery.

You might need to implement a world-blocking event, that is, everything in the application should halt until the distribution code completes and sends. It's certainly not ideal for efficient runtimes, but if even-balance is the goal some things gotta be let go of.

Edit: I kind of know what you're attempting to do, but the devil is in the details here. Will there be a meta-thread for thread queues? Should processes always have access to jobs or should they be free to request/be assigned jobs, or free to be idle? Is memory between processors shared (easy async communication) or are we talking a server-rack-switch setup (usually sync communication but sometimes possible but difficult async communication)?
Edited by dharmaBum - 6/10/10 at 10:22pm
Callisto
(13 items)
 
  
CPUMotherboardGraphicsRAM
2500K 4.7ghz @ 1.37v MSI P67A-GD65 EVGA GTX 680 Mushkin Enhanced Redline 8GB (2 x 4GB) DDR3 1866 
Hard DriveOSMonitorPower
Intel SSD 40GB; Seagate Cavier Green 1TB Scientific Linux 6.3/Windoze7 22" Samsung SyncMaster 2232BW Corsair TX850 
  hide details  
Reply
Callisto
(13 items)
 
  
CPUMotherboardGraphicsRAM
2500K 4.7ghz @ 1.37v MSI P67A-GD65 EVGA GTX 680 Mushkin Enhanced Redline 8GB (2 x 4GB) DDR3 1866 
Hard DriveOSMonitorPower
Intel SSD 40GB; Seagate Cavier Green 1TB Scientific Linux 6.3/Windoze7 22" Samsung SyncMaster 2232BW Corsair TX850 
  hide details  
Reply
post #8 of 9
Thread Starter 
Quote:
Originally Posted by dharmaBum View Post
So, if I understand you correctly, each user submission should be evenly distributed between processors?
There are 4 possible types of users submissions. If a user is submitting multiple requests of type A, only one should be processed at at time.

Quote:
Originally Posted by dharmaBum View Post
You could try a pre-processing of each submission, to determine the most efficient - or most balancing - distribution among the currently running processes. This would involve polling for the most available processors and determining where they should go before-hand. That is, scan the whole input to begin with and then, in the code, try to determine the best places for them to be sent. Attach this information to the config file and send it off to a meta-thread for delivery.
I have no idea how many requests, models, or runtime of each calculation at any given time except time of polling.

Quote:
Originally Posted by dharmaBum View Post
You might need to implement a world-blocking event, that is, everything in the application should halt until the distribution code completes and sends. It's certainly not ideal for efficient runtimes, but if even-balance is the goal some things gotta be let go of.
I have no control of the models.




Here's is what I am thinking:
1) Create list of configuration files that have been assigned a model
2) Create list of currently avaliable models
3) If assigned model is inactive, unassign the file. (Will be reassigned later)
4) Check avaliable models status (Idle, Processing A/B/C/D)
5) Check current open request types
6) Model load balance goal for each request type = (Avaliable Models / Request types)
7) Check which request type is doing the worst in meeting load balance goal.
8) Assign this request type's file to an idle model
9) Repeat 7-8 until no more idle models
10) Go back to 1.

Sorry, it's sort of hard to explain in text.... I am just trying to think of any possible holes or better implementations as this process needs to be robust.
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
post #9 of 9
Thread Starter 
Duh... solved it.

Create of lists of requests types.
Count running models types.
Give an idle model to the request type with fewest running models
Repeat.

I don't have to track exact numbers. I just have to give resources to whatever is getting least. This will just about even out the work distribution regardless.
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
Once again...
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 920 [4.28GHz, HT] Asus P6T + Broadcom NetXtreme II VisionTek HD5850 [900/1200] + Galaxy GT240 2x4GB G.Skill Ripjaw X [1632 MHz] 
Hard DriveOSMonitorKeyboard
Intel X25-M 160GB + 3xRAID0 500GB 7200.12 Window 7 Pro 64 Acer H243H + Samsung 226BW XARMOR-U9BL  
PowerCaseMouseMouse Pad
Antec Truepower New 750W Li Lian PC-V2100 [10x120mm fans] Logitech G9 X-Trac Pro 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Load Balancing Psudeocode