This model is a discrete version of a special case of the model earlier considered by Doshi (1983). Annals of the New York Academy of Sciences 357, 249–259 (1980)īader, D., Cong, G.: A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs).We consider a Geo/D/1 queue operating under a hybrid FIFO/LIFO discipline and obtain the waiting distribution. Mandelbrot, B.: Fractal aspects of the iteration of z → λz(1 − z) for complex λ and z. Michael, M.: Hazard pointers: Safe memory reclamation for lock-free objects. Springer, Heidelberg (2010)Īfek, Y., Hakimi, M., Morrison, A.: Fast and scalable rendezvousing. In: D’Ambra, P., Guarracino, M., Talia, D. ACM (2011)Īfek, Y., Korland, G., Natanzon, M., Shavit, N.: Scalable producer-consumer pools based on elimination-diffraction trees. Symposium on Parallelism in Algorithms and Architectures, SPAA, pp. Sundell, H., Gidenstam, A., Papatriantafilou, M., Tsigas, P.: A lock-free algorithm for concurrent bags. Conference on Engineering of Complex Computer Systems, ICECCS, pp.
#QUEUE FIFO VERIFICATION#
ACM (2010)Ĭolvin, R., Groves, L.: Formal verification of an array-based nonblocking queue. Hendler, D., Incze, I., Shavit, N., Tzafrir, M.: Flat combining and the synchronization-parallelism tradeoff. Herlihy, M., Wing, J.: Linearizability: a correctness condition for concurrent objects. Technical Report 2012-04, Department of Computer Sciences, University of Salzburg (June 2012) Kirsch, C.M., Lippautz, M., Payer, H.: Fast and scalable k-FIFO queues. Symposium on Principles of Programming Languages, POPL. Henzinger, T., Kirsch, C.M., Payer, H., Sezgin, A., Sokolova, A.: Quantitative relaxation of concurrent data structures. ACM (1996)Īfek, Y., Korland, G., Yanovsky, E.: Quasi-linearizability: Relaxed consistency for improved concurrency. Symposium on Principles of Distributed Computing, PODC, pp. Michael, M., Scott, M.: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. This process is experimental and the keywords may be updated as the learning algorithm improves. These keywords were added by machine and not by the authors. Moreover, we demonstrate a prototypical controller which identifies optimal k automatically at runtime achieving better performance than with any statically configured k.
We then demonstrate that our algorithms outperform and outscale all state-of-the-art concurrent pool and queue algorithms that we considered in all micro- and most macrobenchmarks. We show experimentally that there exist optimal and robust k that result in best access performance and scalability. Unlike previous designs, however, the algorithms also implement linearizable emptiness (and full) checks without impairing scalability. The presented algorithms enable up to k enqueue and k dequeue operations to be performed in parallel. Logically, a k-FIFO queue can be understood as queue where elements may be dequeued out-of-order up to k − 1, or as pool where the oldest element is dequeued within at most k dequeue operations. We introduce fast and scalable algorithms that implement bounded- and unbounded-size lock-free k-FIFO queues on parallel, shared memory hardware.
0 kommentar(er)
