find shortest queue, stop the loop and start after 5 enqueues.

hello all i have problem, in the loop of queues of a vector,first i need find the shortest queue. when i found the shortest queue it should enqueue 5 times( without searching) After 5 times enqueuing, again the search the search should start, find the shortest queue and so on. can you please tell some ideas how to do this?

i found the shortest queue, by this code. next how to stop the search after i find once the shortest queue and start the loop search again once it enqueue 5 times.

1
2
3
4
5
6
7
8
9
10
#include <vector> 
#include <queue> 
std::vector<std::queue<int> > q
int min_index = 0;
std::size_t size = q.size();
for( i=0; i<size; i++){ //accessing loop of queues
    if(q[min_index].size() > q[i].size())
        min_index = i; // Now q[min_index] is the shortest queue
} 
q[min_index].push(int)
Is my question clear/understandable?
@Coder777 can you please tell me how to proceed with it.
Last edited on
While loop with a proper statement of when you want to stop.
@yelnatz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector> 
#include <queue> 
std::vector<std::queue<int> > q
task t // implemented in the other part of the program
while(q[min_index].size()!=q[min_index].size()+5) // check whether current min_index  queue's size is increased 5 more times if not goto enqueue
        {
        goto enqueue;
        }

    int min_index = 0;

    std::size_t size = q.size();
    for( i=0; i<size; i++){ //accessing loop of queues
        if(q[min_index].size() > q[i].size())
            min_index = i; // Now q[min_index] is the shortest queue
    } 
    enqueue:  
    q[min_index].push(Task);

i need to do something like the code above, could you please tell me how to do it correctly?
Last edited on
You want to push 5 times and then look for the queue with the lowest size again?

1
2
3
4
5
6
7
8
9
10
11
12
while( statement ){ // change statement to when you want to stop
 ...
 // look for min_index, you have this already
 ...

 // push 5 times
 for( int i = 0; i < 5; i++ ){
  q[min_index].push(Task);
 }
 // finished enqueueing 5 times, go back to top of while loop
 // and look for minimum again
}

Last edited on
@yelnatz i need to find the lowest size queue and the next 5 tasks should get enqueued to the lowest size queue, and then again the start the search again and enqueue next 5 and so on.

the above mentioned code by you does the same? i think its enqueuing same task 5 times
It does enqueue same task 5 times, but that's how you enqueue 5 times.

How does your code get tasks?
@yelnatz
my paradigm is basically related to scheduling of tasks
My code gets the tasks from the nodes and graphs (Multi rate synchronous data flow paradigm), which it gets from other part of library files.

so overall, first the task find the lowest size queue and enqueue in it, the oncoming next 5 tasks also enqueue on the same shortest queue. After this again start the search.

so its like dont 'search every time' or 'search after some condition' .
Last edited on
So you mean, only search for a new min after you've added to the current min 5 times?

Then do some sort of counter that keeps track how many times you've enqueued a task. If the counter exceeds 5, you search for a new min and reset the counter to 0.
@yelnatz that would be a good idea, but could you please tell me how to that correctly with the 'Statements' and 'loops'.
If you can clarify when you get tasks or if you always have tasks, that'd be great. Is it event based? Like do you call this piece of code whenever you receive a task? Do you run the code when you have all the tasks and just want to divide the work? etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int counter = 0;

// get first min
...
// before we move on, we have first min determined

if ( counter >= 5 ){
  // look for new min
 ...
 // counter reset
 counter = 0;
}

// add to queue
...

// increase counter
counter ++;





@yelnatz
If you can clarify when you get tasks or if you always have tasks
In my paradigm always i will be getting the tasks from the graphs and nodes of the data flow graphs.

Is it event based? Like do you call this piece of code whenever you receive a task?
Yes, whenever a task is ready, this piece of code (function) is called.

1
2
3
4
5
6
7
8
9
10
11
void enqueue(scheduler::task )
{
task t;

//find the minimum queue among the loop of queues


// enqueue in minimum queue
q[min_index].push(t)

}


Do you run the code when you have all the tasks and just want to divide the work
I just need the divide the tasks among the queues, whenever the tasks is received

information on SDF dataflow graphs http://www.imit.kth.se/courses/IL2212/0910/lectures/SDF_Handout.pdf

information on work stealing schedulers
http://stackoverflow.com/questions/2101789/implementation-of-a-work-stealing-queue-in-c-c?rq=1

i am trying to modify the work stealing scheduler idea, and develop a new idea called work delegation scheduler, where jobs are delegated to the minimum size local queues

Is it clear now? please let me know if you want more information
Last edited on
Something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// global variables 
std::vector<std::queue<int> > q;
int counter = 10; // start somewhere > 5 so first call of function triggers search for new min
int min_index = 0;

void enqueue(scheduler::task new_task) { 
 if ( counter > 5 ){
  // look for new min
  std::size_t size = q.size();
  for( i=0; i<size; i++){ 
    if(q[min_index].size() > q[i].size())
     min_index = i; 
  } 
  // counter reset
  counter = 0;
 }

 // enqueue in minimum queue
 q[min_index].push(new_task)

 // increase counter
 counter ++;
}
@yelnatz
1
2
3
4
// global variables 
std::vector<std::queue<int> > q;
int counter = 10; // start somewhere > 5 so first call of function triggers search for new min
int min_index = 0;


int min_index = 0; is there any particular reasoning for setting min_index as a global variable?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void enqueue(scheduler::task new_task) { 
if ( counter > 5 ){
  // look for new min
  std::size_t size = q.size();
  for( i=0; i<size; i++){ 
    if(q[min_index].size() > q[i].size())
     min_index = i; 
  } 
  // counter reset
  counter = 0;
 }

// enqueue in minimum queue
 q[min_index].push(new_task)

 // increase counter
 counter ++;
}


so every time the new minimum is obtained, counter is reset and a task is enqueued and counter is incremented by 1. so this incremented value will get updated to the int counter=10; value declared in the global variables everytime?



Last edited on
is there any particular reasoning for setting min_index as a global variable?
yes, I understand it as yelnatz do.

the idea is that finding the min_index is considered being slow, hence they want to do it just every 5th time around. During not being calculated the min_index must remain like it is, hence it's required to be global.

By the way: the reason for the min_index generally is to stress all threads equally
@coder777 @yelnatz
Instead of 5 ( a random number) i thought of having a number which is reliable and approximate everytime. so i thought of get the difference of min_value size and max_value size for the loop of queues and compare it with the counter each time.

so
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
std::vector<std::queue<int> > q;
// global variables 
int counter = INT_MAX; 
int min_index = 0;
int max_size = -1;

void enqueue(scheduler::task new_task) { 
 if ( counter > diff_size ){
  // look for new min and max
  std::size_t size = q.size();
  for( i=0; i<size; i++){ 
    if(q[min_index].size() > q[i].size())
     min_index = i; 
	 if(q[i].size() > max_size)
        max_size = q[i].size(); 
   	diff_size=max_size - min_index;
 }
  // counter reset
  counter = 0;
 }

 // enqueue in minimum queue
 q[min_index].push(new_task)

 // increase counter
 counter ++;
}


could you please check the above code and check if it is can be done like that.
Last edited on
Yes, it can be done like that. But I wouldn't recommend it. The reason:

max_size and min_index are completely different types of numbers. The result is not predictable (you cannot predict when counter > diff_size will become true), which is more the characteristic of a randomness.

I'd recommend a constant. Then you'll be able to control how often the loops runs. Maybe 5 is not enough (i.e. the system is too busy with the loop) and you need a higher number
@coder777 and @yelnatz thank you very much for your interaction.
Topic archived. No new replies allowed.