Heterogeneous stack sizes?
16 views
Skip to first unread message
Ke Na
Jun 27, 2012, 9:22:31 AM6/27/12
to qthr...@googlegroups.com
Hi Kyle, all,
I am currently evaluating qthread for use as back-end for a higher-level concurrent programming environment.
In that environment we distinguish "control tasks" which are many and lightweight; and "computation tasks" which are fewer and may call 3rd party code with arbitrary levels of recursion. These two task classes are currently implemented with a custom low-level threading library which supports "big tasks" and "small tasks": big tasks have 8MB thread stacks, small tasks have 2-4KB stacks. The exact stack size is not configured dynamically per task but instead per class at initialization.
Now I am trying to "emulate" this behavior with qthread. The obvious first solution is to configure all qthreads to use 8MB stacks, but that is inefficient. The "best" solution would be to introduce different stack classes in the qthread library that use different memory pools for stack allocation, but I surmise that is quite some work. So in the meantime I am thinking of creating a wrapper around qthred_fork that provides the following entry function:
typedef struct {
aligned_t (*fun)(void*);
void *arg;
int type;
} my_fun_def;
aligned_t wrapper(void* arg)
{
my_fun_def* s = (fun_def*)arg;
if (s->type == BIG)
{
void *newstack = qpool_alloc(...);
run_with_custom_stack(newstack, s->fun, s->arg, &r);
qpool_free(..., newstack);
return r;
}
else
return s->fun(s->arg);
}
Then I was thinking of implementing run_with_custom_stack() with a macro which uses inline assembly to override the stack pointer before calling the function.
What do you think of this solution? Would the qthread library accept the new stack pointer if the called function suspends the qthread? Is there maybe a qthread internal function I could use that achieves the same?
Regards,
--
k
I am currently evaluating qthread for use as back-end for a higher-level concurrent programming environment.
In that environment we distinguish "control tasks" which are many and lightweight; and "computation tasks" which are fewer and may call 3rd party code with arbitrary levels of recursion. These two task classes are currently implemented with a custom low-level threading library which supports "big tasks" and "small tasks": big tasks have 8MB thread stacks, small tasks have 2-4KB stacks. The exact stack size is not configured dynamically per task but instead per class at initialization.
Now I am trying to "emulate" this behavior with qthread. The obvious first solution is to configure all qthreads to use 8MB stacks, but that is inefficient. The "best" solution would be to introduce different stack classes in the qthread library that use different memory pools for stack allocation, but I surmise that is quite some work. So in the meantime I am thinking of creating a wrapper around qthred_fork that provides the following entry function:
typedef struct {
aligned_t (*fun)(void*);
void *arg;
int type;
} my_fun_def;
aligned_t wrapper(void* arg)
{
my_fun_def* s = (fun_def*)arg;
if (s->type == BIG)
{
void *newstack = qpool_alloc(...);
run_with_custom_stack(newstack, s->fun, s->arg, &r);
qpool_free(..., newstack);
return r;
}
else
return s->fun(s->arg);
}
Then I was thinking of implementing run_with_custom_stack() with a macro which uses inline assembly to override the stack pointer before calling the function.
What do you think of this solution? Would the qthread library accept the new stack pointer if the called function suspends the qthread? Is there maybe a qthread internal function I could use that achieves the same?
Regards,
--
k
Wheeler, Kyle Bruce
Jun 27, 2012, 11:18:21 AM6/27/12
to <qthreads@googlegroups.com>
Hello,
We've pondered establishing some kind of a fork where you specify the stack size, but have yet to really find a really strong use-case to justify the effort. So, for the moment, let's examine the possibilities and the requirements of your task categories.
I think my first, and most important question is: do control tasks block? If not, the actual overhead for using a larger stack for them is minimal, since the stack is only allocated when the task actually executes, and since the stacks are pooled, there is no more (computational) overhead for allocating an 8MB stack than there is for allocating a 2k stack. Further, if they do not block, you may be able to use "simple" tasks for your control tasks instead of standard tasks (see the SPAWN_SIMPLE flag to qthread_spawn()). Simple tasks are (admittedly) not well-documented, but essentially a simple task is treated as a simple function-call from the underlying worker, rather than a context-swap (i.e. it's cheaper and faster to execute as well), and so borrows its stack, rather than receiving its own stack; the only functional restriction being that simple tasks cannot perform blocking operations.
However, if control tasks do block (and frequently), then I agree, large stacks are an unfortunately inefficient route to take. The way the contexts are handled, yes, I think your wrapper would work just fine for "upgrading" a small stack to a bigger one - it's an interesting idea. A little extra overhead for changing stacks, but relatively simple (keep in mind, this won't behave itself (or report correct values) with rlimit). However, I think we can do better by integrating the multiple stack sizes into the concept of a qthread. Since, obviously, we would rather have stacks be specific sizes, let's brainstorm about how to do this in a more generic way. What if we created a fork-with-stack-size option that rounded those sizes into buckets, and then only created memory pools for those buckets on an as-needed basis?
~Kyle
--
Kyle B. Wheeler
Dept. 1423: Scalable System Software
Sandia National Laboratories
505-844-0394
We've pondered establishing some kind of a fork where you specify the stack size, but have yet to really find a really strong use-case to justify the effort. So, for the moment, let's examine the possibilities and the requirements of your task categories.
I think my first, and most important question is: do control tasks block? If not, the actual overhead for using a larger stack for them is minimal, since the stack is only allocated when the task actually executes, and since the stacks are pooled, there is no more (computational) overhead for allocating an 8MB stack than there is for allocating a 2k stack. Further, if they do not block, you may be able to use "simple" tasks for your control tasks instead of standard tasks (see the SPAWN_SIMPLE flag to qthread_spawn()). Simple tasks are (admittedly) not well-documented, but essentially a simple task is treated as a simple function-call from the underlying worker, rather than a context-swap (i.e. it's cheaper and faster to execute as well), and so borrows its stack, rather than receiving its own stack; the only functional restriction being that simple tasks cannot perform blocking operations.
However, if control tasks do block (and frequently), then I agree, large stacks are an unfortunately inefficient route to take. The way the contexts are handled, yes, I think your wrapper would work just fine for "upgrading" a small stack to a bigger one - it's an interesting idea. A little extra overhead for changing stacks, but relatively simple (keep in mind, this won't behave itself (or report correct values) with rlimit). However, I think we can do better by integrating the multiple stack sizes into the concept of a qthread. Since, obviously, we would rather have stacks be specific sizes, let's brainstorm about how to do this in a more generic way. What if we created a fork-with-stack-size option that rounded those sizes into buckets, and then only created memory pools for those buckets on an as-needed basis?
~Kyle
Kyle B. Wheeler
Dept. 1423: Scalable System Software
Sandia National Laboratories
505-844-0394
Raphael 'kena' Poss
Jun 27, 2012, 1:54:34 PM6/27/12
to qthr...@googlegroups.com
Hi Kyle,
many thanks for your answer.
I am glad to learn about simple tasks, as they may prove useful for other reasons. Unfortunately the control tasks I mentioned do block: all tasks including control tasks would be mutually involved in dataflow synchronization patterns.
As to your suggestion:
Op 27 jun 2012, om 17:18 heeft Wheeler, Kyle Bruce het volgende geschreven:
> However, I think we can do better by integrating the multiple stack sizes into the concept of a qthread. Since, obviously, we would rather have stacks be specific sizes, let's brainstorm about how to do this in a more generic way. What if we created a fork-with-stack-size option that rounded those sizes into buckets, and then only created memory pools for those buckets on an as-needed basis?
I agree that the number of stack size classes should be dynamically configurable; however I believe there is no need for supporting the definition of new classes after initialization.
My intuition here would be along the following lines:
- create an API to register a new "thread class". This registration function would then be in charge of creating the memory pool that stacks for threads of that class would be allocated from.
- a thread class would then be identified with some sort of "class ID";
- the class ID would then be passed to a new fork-specific-class API;
- Each class would have attached attributes to it, such as desired stack size as mentioned above, but also possibly (that's another interest of ours) a template for thread-specific data.
What do you think?
--
Raphael 'kena' Poss · r.c....@uva.nl
http://staff.science.uva.nl/~poss/
many thanks for your answer.
I am glad to learn about simple tasks, as they may prove useful for other reasons. Unfortunately the control tasks I mentioned do block: all tasks including control tasks would be mutually involved in dataflow synchronization patterns.
As to your suggestion:
Op 27 jun 2012, om 17:18 heeft Wheeler, Kyle Bruce het volgende geschreven:
> However, I think we can do better by integrating the multiple stack sizes into the concept of a qthread. Since, obviously, we would rather have stacks be specific sizes, let's brainstorm about how to do this in a more generic way. What if we created a fork-with-stack-size option that rounded those sizes into buckets, and then only created memory pools for those buckets on an as-needed basis?
My intuition here would be along the following lines:
- create an API to register a new "thread class". This registration function would then be in charge of creating the memory pool that stacks for threads of that class would be allocated from.
- a thread class would then be identified with some sort of "class ID";
- the class ID would then be passed to a new fork-specific-class API;
- Each class would have attached attributes to it, such as desired stack size as mentioned above, but also possibly (that's another interest of ours) a template for thread-specific data.
What do you think?
--
Raphael 'kena' Poss · r.c....@uva.nl
http://staff.science.uva.nl/~poss/
Wheeler, Kyle Bruce
Jun 27, 2012, 5:57:58 PM6/27/12
to <qthreads@googlegroups.com>
Hi Raphael,
Hmm. Given the name, I suppose it makes sense that the control tasks would block. I assume the big tasks would block too?
We already have the concept of task teams… I wonder if we can re-use this idea to specify the stack size. That might be an interesting option. As far as templating TSP… that's certainly possible, though I'm not sure that the runtime is the right place to do that.
Does anyone else have any thoughts on the matter?
Hmm. Given the name, I suppose it makes sense that the control tasks would block. I assume the big tasks would block too?
We already have the concept of task teams… I wonder if we can re-use this idea to specify the stack size. That might be an interesting option. As far as templating TSP… that's certainly possible, though I'm not sure that the runtime is the right place to do that.
Does anyone else have any thoughts on the matter?
Raphael 'kena' Poss
Jun 27, 2012, 6:41:04 PM6/27/12
to qthr...@googlegroups.com
Op 27 jun 2012, om 23:57 heeft Wheeler, Kyle Bruce het volgende geschreven:
> Hmm. Given the name, I suppose it makes sense that the control tasks would block. I assume the big tasks would block too?
> We already have the concept of task teams… I wonder if we can re-use this idea to specify the stack size.
> That might be an interesting option. As far as templating TSP… that's certainly possible, though I'm not sure that the runtime is the right place to do that.
Stark, Dylan
Jun 27, 2012, 7:02:52 PM6/27/12
to <qthreads@googlegroups.com>
On Jun 27, 2012, at 4:41 PM, Raphael 'kena' Poss wrote:
Op 27 jun 2012, om 23:57 heeft Wheeler, Kyle Bruce het volgende geschreven:
Hmm. Given the name, I suppose it makes sense that the control tasks would block. I assume the big tasks would block too?
yes, sure
We already have the concept of task teams… I wonder if we can re-use this idea to specify the stack size.
Possibly but aren't teams supposed to group "related activities" under the same shepherds? I'm not sure the abstraction matches the problem at hand, but I could look into it.
There is no relationship between teams and shepherds: the "coverage" of a team over a set of shepherds is just shepherds that are currently executing tasks in that team, and can evolve over time due to load balancing, etc. That said, I think it would be
awkward to use that interface and/or infrastructure to support associating attributes like stack size with tasks. It is likely that someone will want to have a team represent some application-level grouping (e.g., all tasks performing a graph search), and
that some of those tasks will be control tasks and some big tasks. The current team concept does not support having a task belong to two teams.
Dylan
That might be an interesting option. As far as templating TSP… that's certainly possible, though I'm not sure that the runtime is the right place to do that.
Well if you know of any better place... :)
--
Raphael 'kena' Poss · r.c....@uva.nl
http://staff.science.uva.nl/~poss/
Reply all
Reply to author
Forward
0 new messages