Mercurial > hg > truffle
changeset 12087:61521bd65100
8022784: TaskQueue misses minimal documentation and references for analysis
Summary: Add appropriate documentation and references to publication to allow easier analysis of the TaskQueue implementation.
Reviewed-by: dholmes, ehelin
| author | tschatzl |
|---|---|
| date | Wed, 21 Aug 2013 10:32:02 +0200 |
| parents | 31f220c1f789 |
| children | cb9da55b1990 |
| files | src/share/vm/utilities/taskqueue.hpp |
| diffstat | 1 files changed, 33 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/vm/utilities/taskqueue.hpp Tue Aug 20 10:02:38 2013 -0700 +++ b/src/share/vm/utilities/taskqueue.hpp Wed Aug 21 10:32:02 2013 +0200 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2001, 2013, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -132,6 +132,8 @@ } #endif // TASKQUEUE_STATS +// TaskQueueSuper collects functionality common to all GenericTaskQueue instances. + template <unsigned int N, MEMFLAGS F> class TaskQueueSuper: public CHeapObj<F> { protected: @@ -249,7 +251,36 @@ TASKQUEUE_STATS_ONLY(TaskQueueStats stats;) }; - +// +// GenericTaskQueue implements an ABP, Aurora-Blumofe-Plaxton, double- +// ended-queue (deque), intended for use in work stealing. Queue operations +// are non-blocking. +// +// A queue owner thread performs push() and pop_local() operations on one end +// of the queue, while other threads may steal work using the pop_global() +// method. +// +// The main difference to the original algorithm is that this +// implementation allows wrap-around at the end of its allocated +// storage, which is an array. +// +// The original paper is: +// +// Arora, N. S., Blumofe, R. D., and Plaxton, C. G. +// Thread scheduling for multiprogrammed multiprocessors. +// Theory of Computing Systems 34, 2 (2001), 115-144. +// +// The following paper provides an correctness proof and an +// implementation for weakly ordered memory models including (pseudo-) +// code containing memory barriers for a Chase-Lev deque. Chase-Lev is +// similar to ABP, with the main difference that it allows resizing of the +// underlying storage: +// +// Le, N. M., Pop, A., Cohen A., and Nardell, F. Z. +// Correct and efficient work-stealing for weak memory models +// Proceedings of the 18th ACM SIGPLAN symposium on Principles and +// practice of parallel programming (PPoPP 2013), 69-80 +// template <class E, MEMFLAGS F, unsigned int N = TASKQUEUE_SIZE> class GenericTaskQueue: public TaskQueueSuper<N, F> {