Is there an algorithm to determine the amount of work needed to keep workers busy?

I wrote a multi-threaded program that randomly generates strings, and after generating, checks to see if the string contains a certain value. Namely, StringGenerator and StringChecker. What I’m trying to figure out is how many StringGenerator threads I would need in order to keep StringChecker busy.

All StringGenerator threads have a reference to a Queue that contains all of the Strings needed to be checked, and when they generate a String, it gets added to the Queue. All StringChecker threads also have a reference to the same Queue and poll it to get the next string, and checks to see if it contains the keyword.

Because generating the Strings takes more time than checking them, what I want to know is if there are any equations, algorithms or analyses that can be done on the code that can help tell me approximately how many threads of each I will need such that the sum of all Strings generated by the StringGenerators is as close to the number of strings checked by the StringCheckers as possible.

You can’t have more productive threads than you have processors. (I’m ignoring I/O for now.) Lets suppose maxThreads is the total maximum number of threads you want to have. This is a soft limit. It may get exceeded temporarily, but the excess will correct itself.

Have a queue of unchecked strings, initially empty. Start one StringChecker thread.

Every time a StringChecker sees the queue empty, it starts a new StringGenerator thread. If the total number of threads now exceed maxThreads and this is not the only StringChecker thread, it stops. Otherwise, it pulls a string from the queue and checks it.

Every time a StringGenerator has a string ready to be checked but finds the queue is full, it starts a new StringChecker thread. After waiting for the queue to unblock and let it put its string into the queue, if the total number of threads now exceeds maxThreads and it is not the last StringGenerator, it stops.

Better Answer

I was playing out in my mind how this system and the one described by @rwong would behave, and realized we’re going at this all wrong. How long it takes to generate a string versus how long it takes to check one is irrelevant. When the system reaches steady state, it will be checking strings at exactly the same rate it generates them. stringsGenerated = stringsChecked + stringsInQueue + stringsBeingChecked, and the last two terms are both small and bounded.

That means you may as well start as many threads as you deem useful, and have each thread:

loop
    generate a string
    check it
end loop

I see that @Doval had the same idea, so I +1ed his comment.

Assuming that the time it takes to generate and check strings is fairly regular, you can hard code a ratio after doing some timing. Suppose generating a string takes on average N nanoseconds, and checking it takes M nanoseconds. If it takes three times as long to generate as it does to check, that is if N / M = 3, then there should be three times as many generators as there are checkers – three generators for each checker. So do some profiling, find some averages, and figure out what ratio you need.

There is another approach. This is similar to @ganbustein’s answer, but with one difference. It is known as the Task parallelism paradigm.

In task parallelism,

All execution is decomposed, and the decomposed tasks are packaged into tasks.
(Also known as “closures”, which means a self-contained unit of executable code and all data that is needed. If any data isn’t immediately available (i.e. dependent on another task), this dependency is noted by the task parallelism engine, and the executable code will deal with it by wrapping it in a Future.)
The dependencies between tasks are established.
Tasks that are ready to execute are pushed into a common queue.
Any CPU that is available, will grab any task that is on the front of the common queue.
After executing the task, any subsequent tasks whose data dependency become satisfied will now be added to the common queue.

The key difference between Task Parallelism and @ganbustein’s answer is this: “there is no affinity between task types, threads, or CPU cores.”

To restate in a simple sentence, “any thread can execute any task type that shows up on the queue.”

Given your example, you can instantiate as many threads as you have CPU cores, and all of these threads will run the following infinite loop:

If there is a string in the “waiting to be checked” queue, it will be popped and checked.
(In task-oriented thinking, this is a simplification of executing the StringCheckerTask.)
Otherwise, generate a new random string and add to the “waiting to be checked” queue.
(In task-oriented thinking, this is a simplification of executing the StringGeneratorTask.)
Keep looping until interrupted.

Expected result: You will see that all cores are fully occupied. Make sure your CPU has good ventilation.

Side effects: By maximizing CPU utilization, you will notice that it places heavy stress on your implementation of Queue structure. All of the CPUs will be reading and writing this queue, so this creates lots of memory access conflicts. (If your queue is not thread-safe, it will also start losing or corrupting data pretty quickly.)

Filed under: softwareengineering - @ 20:21

Thẻ: algorithms, concurrency, multithreading

Thiết kế website giá rẻ

Danh mục

Is there an algorithm to determine the amount of work needed to keep workers busy?