simple work-requesting scheme...

simple work-requesting scheme...

Post by Chris M. T » Tue, 24 Aug 2010 09:14:21


For more info on "work-requesting" refer to the following article:

http://www.yqcomputer.com/
(read all...)


Here is a brief high level description of a simple work-requesting idea I am
thinking about implementing:

A worker entity is comprised of two event objects, a Petersons mutex, work
queue, work request stack and two threads bound to the same CPU. One thread
is the main worker, and the other is dedicated to work request processing.
The work request thread simply waits on an event object and processes work
requests from other worker entities. This involves locking the Petersons
mutex and transferring some work over to the requesting worker. The mutex
lock/unlock does not need any explicit memory barriers because the main
worker thread and the work request thread are bound to the exact same CPU.
That's fairly efficient for the main worker thread because it means it does
not need any RMW atomic ops and/or memory barriers for enqueuing/dequeueing
local work. Also, contention on the Petersons mutex should be minimal
because the frequency of work requests should be fairly low anyway...


Also, WRT the following sentence from the article linked to above:

"With work-requesting a thief thread is able to get some work
only if a victim thread condescends to send it (which it is just
unable to do if it is de-scheduled by an OS)."

Well, I think that the idea of having two threads per-cpu could address the
"reactivity" problem with work-stealing that Dmitriy is describing here. The
fact that the main worker thread is currently de-scheduled by the OS does
not prevent work requests from being processed...


Any thoughts?




Thank you.
 
 
 

1. I submitted MY work REQUEST, 2003, BUT My WORK request is just now

2. Needed: mergesort (disk-to-disk) in scheme; statical scheme code analyzer; scheme profiler

I am developing a code for symbolical computations (not general
purpose) with quadratic surds and rationals, some thousand - thousand-
a-half lines of GNU-MIT scheme, and I am encountering from time to
time memory related errors as "Out of memory" and "Maximum recursion
depth exceeded".

An important part of my code deals with merging two sorted files, each
line beeing a scheme object, into a unique sorted file. I am using no
ready-made libraries.
Maybe someone can help me in finding a library, defining a function
that takes two input files, one output file and a predicate for
comparing two elements, and manages the work by itself?

Some other questions:
Is there a way to extract a dependency graph from my rather spaghetti
code?
Is there a way to decide statically wheter my functions do really
always behave as tail-recursive (as I intended)?
Is there a way of profiling my scheme code, so that I can select the
data on which my code behaves badly?

Thanks in advance

Alex

3. New Wraith Scheme, Pixie Scheme II, and Pixie Scheme III, and source available now.

4. sql2005 simple 'update where' request with IF that does not work

5. A simple answer for a simple request

6. simple simple request... java darwing lib

7. Parsing HTML in scheme - request for code critique

8. broadcasting request to LIMY Scheme maintainers: char-infty

9. Complicating my AD Scheme -- Request for Advice

10. requests with a "WHERE" works, request with no "WHERE" doesn't

11. Maintenance Work Request Form, Request to repair broken machinery

12. Color scheme feedback request: Baycomb

13. Java Class Plugin Scheme Help Request

14. Request/Demand in Database scheme

15. Work Around Requested: Error executing child request for SignInConfirm.aspx.