Index: doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision 289c7d2d08324b12fa247f070f64d4ffc48bcd09) +++ doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision 4a40f695cc241cf2f33832c81c6644b6c5266085) @@ -1,3 +1,4 @@ -\documentclass[11pt,fullpage]{article} +\documentclass[11pt]{article} +\usepackage{fullpage} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} @@ -10,6 +11,6 @@ \usepackage{glossaries} \usepackage{textcomp} -\usepackage{geometry} -\usepackage{float} +%\usepackage[margin=1in]{geometry} +%\usepackage{float} % cfa macros used in the document @@ -128,7 +129,8 @@ A simple ready-queue can be built from a FIFO queue, user-threads are pushed onto the queue when they are ready to run and processors (kernel-threads acting as virtual processors) pop the user-threads from the queue and execute them. Using Trevor's paper\cit as basis, it is simple to build a relaxed FIFO list that is fast and scalable for loaded or overloaded systems. The described queue uses an array of underlying strictly FIFO queues as shown in Figure~\ref{fig:base}\footnote{For this section, the number of underlying queues is assumed to be constant, Section~\ref{sec:resize} will discuss resizing the array.}. Pushing new data is done by selecting one of these underlying queues at random, recording a timestamp for the push and pushing to the selected queue. Popping is done by selecting two queues at random and popping from the queue for which the head has the oldest timestamp. A higher number of underlying queues leads to less contention on each queue and therefore better performance. In a loaded system, it is higly likely the queues are non-empty, i.e., several tasks are on each of the underlying queues. This means that selecting a queue at random to pop from is higly likely to yield a queue with available items. In Figure~\ref{fig:base}, ignoring the ellipsis, the chances of getting an empty queue is 2/7 per pick, meaning two randoms pick will yield an item approximately 9 times out of 10. -\begin{figure}[H] - \begin{center} - {\resizebox{0.8\textwidth}{!}{\input{base}}} +\begin{figure} + \begin{center} +% {\resizebox{0.8\textwidth}{!}{\input{base}}} + \input{base} \end{center} \caption{Relaxed FIFO list at the base of the scheduler: an array of strictly FIFO lists. } @@ -136,7 +138,8 @@ \end{figure} -\begin{figure}[H] - \begin{center} - {\resizebox{0.8\textwidth}{!}{\input{empty}}} +\begin{figure} + \begin{center} +% {\resizebox{0.8\textwidth}{!}{\input{empty}}} + \input{empty} \end{center} \caption{``More empty'' state of the queue: the array contains many empty cells.} @@ -146,5 +149,5 @@ When the ready queue is "more empty", i.e., several of the inner queues are empty, selecting a random queue for popping is less likely to yield a valid selection and more attempts need to be made, resulting in a performance degradation. Figure~\ref{fig:empty} shows an example with fewer elements where the chances of getting an empty queue is 5/7 per pick, meaning two randoms pick will yield an item only half the time. Since the overarching queue is not empty, the pop operation \emph{must} find an element before returning and therefore must retry. Overall performance is therefore influenced by the contention on the underlying queues and pop performance is influenced by the items density. This leads to four performance cases, as depicted in Table~\ref{tab:perfcases}. -\begin{table}[H] +\begin{table} \begin{center} \begin{tabular}{|c|c|c|} @@ -162,5 +165,5 @@ A bitmask can be used to identify which inner queues are currently in use, as shown in Figure~\ref{fig:emptybit}. This means that processors can often find user-threads in constant time, regardless of how many underlying queues are empty. Furthermore, modern x86 CPUs have an extension (BMI2) which allow using the bitmask with very little overhead compared to a filled readyqueue, offerring decent performance even in cases with many empty inner queues. However, this technique has its limits, with a single word\footnote{Word refers here to however many bits can be written atomicly.} bitmask, the total number of underlying queues in the overarching queue is limited to the number of bits in the word. With a multi-word bitmask, this maximum limit can be increased arbitrarily, but it is not possible to check if the queue is empty by reading the bitmask atomicly. A dense bitmap, i.e., either a single word bitmask or a multi word bitmask where all words are densely packed, also causes additionnal problems in case~C (Table~\ref{tab:perfcases}), which the increased contention on the bitmask both causes new performance degradation and means the accuracy of the bitmask is less reliable due to more hardware threads potentially racing to read and/or update that information. -\begin{figure}[H] +\begin{figure} \begin{center} {\resizebox{0.8\textwidth}{!}{\input{emptybit}}} @@ -172,5 +175,5 @@ Another approach is to use a hiearchical data structure, for example Figure~\ref{fig:emptytree}. Creating a tree of nodes to reduce contention has been shown to work in similar cases\cit(SNZI: Scalable NonZero Indicators)\footnote{This particular paper seems to be patented in the US. How does that affect \CFA? Can I use it in my work?}. However, this approach may lead to poorer performance in case~B (Table~\ref{tab:perfcases}) due to the inherent pointer chasing cost and already low contention cost in that case. -\begin{figure}[H] +\begin{figure} \begin{center} {\resizebox{0.8\textwidth}{!}{\input{emptytree}}} @@ -193,7 +196,8 @@ The \CFA runtime system currently handles dynamically adding and removing processors from clusters at any time. Since this is part of the existing design, the proposed scheduler must also support this behaviour. However, dynamicly resizing the clusters is considered a rare event associated with setup, teardown and major configuration changes. This assumptions is made both in the design of the proposed scheduler as well as in the original design of the \CFA runtime system. As such, the proposed scheduler must honor the correctness of these behaviour but does not have any performance objectives with regards to resizing a cluster. How long adding or removing processors take and how much this disrupts the performance of other threads is considered a secondary concern since it should be amortized over long period of times. However, as mentionned in Section~\ref{sec:queue}, contention on the underlying queues can have a direct impact on performance, the number of underlying queues must therefore be adjusted as the number of processors grows or shrinks. Since the underlying queues are stored in a dense array, changing the number of queues requires resizing the array and therefore moving it. This can introduce memory reclamation problems if not done correctly. -\begin{figure}[H] - \begin{center} - {\resizebox{0.8\textwidth}{!}{\input{resize}}} +\begin{figure} + \begin{center} +% {\resizebox{0.8\textwidth}{!}{\input{resize}}} + \input{resize} \end{center} \caption{Copy of data structure shown in Figure~\ref{fig:base}. The cells of the array can be modified concurrently but resizing the array, which requires moving it, is not safe to do concurrently. This can also be true of the accompanying data structures used to find non-empty queues.} Index: doc/theses/thierry_delisle_PhD/comp_II/img/base.fig =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/img/base.fig (revision 289c7d2d08324b12fa247f070f64d4ffc48bcd09) +++ doc/theses/thierry_delisle_PhD/comp_II/img/base.fig (revision 4a40f695cc241cf2f33832c81c6644b6c5266085) @@ -8,119 +8,107 @@ -2 1200 2 -6 1200 3300 2100 4950 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 4950 1650 3975 +6 2400 3075 3000 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 3750 1425 4140 1875 4140 2100 3750 1875 3360 1425 3360 - 1200 3750 + 3000 3335 2850 3075 2550 3075 2400 3335 2550 3595 2850 3595 + 3000 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 -6 -6 1200 2175 2100 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 3825 1650 2850 +6 2400 2175 3000 3375 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 2625 1425 3015 1875 3015 2100 2625 1875 2235 1425 2235 - 1200 2625 + 3000 2435 2850 2175 2550 2175 2400 2435 2550 2695 2850 2695 + 3000 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3375 2700 2700 -6 -6 3000 3375 3900 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 3450 5025 3450 4050 +6 3600 2175 4200 3375 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 3000 3825 3225 4215 3675 4215 3900 3825 3675 3435 3225 3435 - 3000 3825 + 4200 2435 4050 2175 3750 2175 3600 2435 3750 2695 4050 2695 + 4200 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 3375 3900 2700 -6 -6 4800 3375 5700 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 5025 5250 4050 +6 3600 3075 4200 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 3825 5025 4215 5475 4215 5700 3825 5475 3435 5025 3435 - 4800 3825 + 4200 3335 4050 3075 3750 3075 3600 3335 3750 3595 4050 3595 + 4200 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 4200 3900 3600 -6 -6 6600 3375 7500 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 7050 5025 7050 4050 +6 4200 3075 4800 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 6600 3825 6825 4215 7275 4215 7500 3825 7275 3435 6825 3435 - 6600 3825 + 4800 3335 4650 3075 4350 3075 4200 3335 4350 3595 4650 3595 + 4800 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4500 4200 4500 3600 -6 -6 4800 2175 5700 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 3825 5250 2850 +6 4800 3075 5400 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 2625 5025 3015 5475 3015 5700 2625 5475 2235 5025 2235 - 4800 2625 + 5400 3335 5250 3075 4950 3075 4800 3335 4950 3595 5250 3595 + 5400 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 -6 -6 3000 2175 3900 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 3450 3825 3450 2850 +6 4800 2175 5400 3375 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 3000 2625 3225 3015 3675 3015 3900 2625 3675 2235 3225 2235 - 3000 2625 + 5400 2435 5250 2175 4950 2175 4800 2435 4950 2695 5250 2695 + 5400 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 3375 5100 2700 -6 -6 4800 975 5700 2625 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 2625 5250 1650 +6 4800 1275 5400 2475 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 1425 5025 1815 5475 1815 5700 1425 5475 1035 5025 1035 - 4800 1425 + 5400 1535 5250 1275 4950 1275 4800 1535 4950 1795 5250 1795 + 5400 1535 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 2475 5100 1800 -6 -6 6600 2175 7500 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 7050 3825 7050 2850 +6 6000 2175 6600 3375 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 6600 2625 6825 3015 7275 3015 7500 2625 7275 2235 6825 2235 - 6600 2625 + 6600 2435 6450 2175 6150 2175 6000 2435 6150 2695 6450 2695 + 6600 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 3375 6300 2700 -6 -6 3900 3375 4800 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 4350 5025 4350 4050 +6 6000 3075 6600 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 3900 3825 4125 4215 4575 4215 4800 3825 4575 3435 4125 3435 - 3900 3825 + 6600 3335 6450 3075 6150 3075 6000 3335 6150 3595 6450 3595 + 6600 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 4200 6300 3600 -6 -6 75 2850 1650 5775 -6 75 2850 1650 5775 -4 0 0 50 -1 0 22 0.0000 2 315 930 75 3150 Ready\001 -4 0 0 50 -1 0 22 0.0000 2 240 1170 75 3525 Threads\001 -4 0 0 50 -1 0 22 0.0000 2 315 1470 150 5700 of Queues\001 -4 0 0 50 -1 0 22 0.0000 2 315 840 150 5325 Array\001 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 -6 --6 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 1200 4500 8700 4500 8700 5400 1200 5400 1200 4500 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 2100 4500 2100 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3000 4500 3000 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3900 4500 3900 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 4500 4800 5325 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 5250 4800 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 5700 4500 5700 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 6600 4500 6600 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 7500 4500 7500 5400 -4 0 0 50 -1 0 22 0.0000 2 45 270 7950 5025 ...\001 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 Index: doc/theses/thierry_delisle_PhD/comp_II/img/empty.fig =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/img/empty.fig (revision 289c7d2d08324b12fa247f070f64d4ffc48bcd09) +++ doc/theses/thierry_delisle_PhD/comp_II/img/empty.fig (revision 4a40f695cc241cf2f33832c81c6644b6c5266085) @@ -8,56 +8,51 @@ -2 1200 2 -6 1200 3300 2100 4950 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 4950 1650 3975 +6 4800 3075 5400 4200 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 3750 1425 4140 1875 4140 2100 3750 1875 3360 1425 3360 - 1200 3750 + 5400 3335 5250 3075 4950 3075 4800 3335 4950 3595 5250 3595 + 5400 3335 -6 -6 1200 2175 2100 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 3825 1650 2850 +6 2400 2175 3000 3375 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 2625 1425 3015 1875 3015 2100 2625 1875 2235 1425 2235 - 1200 2625 + 3000 2435 2850 2175 2550 2175 2400 2435 2550 2695 2850 2695 + 3000 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3375 2700 2700 -6 -6 4800 3375 5700 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 5025 5250 4050 +6 2400 3075 3000 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 3825 5025 4215 5475 4215 5700 3825 5475 3435 5025 3435 - 4800 3825 + 3000 3335 2850 3075 2550 3075 2400 3335 2550 3595 2850 3595 + 3000 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 -6 -6 75 2850 1650 5775 -6 75 2850 1650 5775 -4 0 0 50 -1 0 22 0.0000 2 315 930 75 3150 Ready\001 -4 0 0 50 -1 0 22 0.0000 2 240 1170 75 3525 Threads\001 -4 0 0 50 -1 0 22 0.0000 2 315 1470 150 5700 of Queues\001 -4 0 0 50 -1 0 22 0.0000 2 315 840 150 5325 Array\001 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 -6 --6 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 1200 4500 8700 4500 8700 5400 1200 5400 1200 4500 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 2100 4500 2100 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3000 4500 3000 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3900 4500 3900 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 4500 4800 5325 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 5250 4800 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 5700 4500 5700 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 6600 4500 6600 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 7500 4500 7500 5400 -4 0 0 50 -1 0 22 0.0000 2 45 270 7950 5025 ...\001 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 Index: doc/theses/thierry_delisle_PhD/comp_II/img/emptybit.fig =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/img/emptybit.fig (revision 289c7d2d08324b12fa247f070f64d4ffc48bcd09) +++ doc/theses/thierry_delisle_PhD/comp_II/img/emptybit.fig (revision 4a40f695cc241cf2f33832c81c6644b6c5266085) @@ -8,57 +8,52 @@ -2 1200 2 -6 1200 3300 2100 4950 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 4950 1650 3975 +6 4800 3075 5400 4200 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 3750 1425 4140 1875 4140 2100 3750 1875 3360 1425 3360 - 1200 3750 + 5400 3335 5250 3075 4950 3075 4800 3335 4950 3595 5250 3595 + 5400 3335 -6 -6 1200 2175 2100 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 3825 1650 2850 +6 2400 2175 3000 3375 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 2625 1425 3015 1875 3015 2100 2625 1875 2235 1425 2235 - 1200 2625 + 3000 2435 2850 2175 2550 2175 2400 2435 2550 2695 2850 2695 + 3000 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3375 2700 2700 -6 -6 4800 3375 5700 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 5025 5250 4050 +6 2400 3075 3000 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 3825 5025 4215 5475 4215 5700 3825 5475 3435 5025 3435 - 4800 3825 + 3000 3335 2850 3075 2550 3075 2400 3335 2550 3595 2850 3595 + 3000 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 -6 -6 75 2850 1650 5775 -6 75 2850 1650 5775 -4 0 0 50 -1 0 22 0.0000 2 315 930 75 3150 Ready\001 -4 0 0 50 -1 0 22 0.0000 2 240 1170 75 3525 Threads\001 -4 0 0 50 -1 0 22 0.0000 2 315 1470 150 5700 of Queues\001 -4 0 0 50 -1 0 22 0.0000 2 315 840 150 5325 Array\001 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 -6 --6 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 1200 4500 8700 4500 8700 5400 1200 5400 1200 4500 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 2100 4500 2100 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3000 4500 3000 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3900 4500 3900 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 4500 4800 5325 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 5250 4800 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 5700 4500 5700 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 6600 4500 6600 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 7500 4500 7500 5400 -4 0 0 50 -1 0 22 0.0000 2 45 270 7950 5025 ...\001 -4 0 0 50 -1 0 22 0.0000 2 315 2445 3075 5775 {\\tt[1000100...]}\001 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 +4 0 0 50 -1 5 14 0.0000 2 180 1800 3750 4800 [1000100...]\001 Index: doc/theses/thierry_delisle_PhD/comp_II/img/emptytree.fig =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/img/emptytree.fig (revision 289c7d2d08324b12fa247f070f64d4ffc48bcd09) +++ doc/theses/thierry_delisle_PhD/comp_II/img/emptytree.fig (revision 4a40f695cc241cf2f33832c81c6644b6c5266085) @@ -8,88 +8,86 @@ -2 1200 2 -6 1200 3300 2100 4950 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 4950 1650 3975 +6 4800 3075 5400 4200 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 3750 1425 4140 1875 4140 2100 3750 1875 3360 1425 3360 - 1200 3750 + 5400 3335 5250 3075 4950 3075 4800 3335 4950 3595 5250 3595 + 5400 3335 -6 -6 1200 2175 2100 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 3825 1650 2850 +6 2400 2175 3000 3375 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 2625 1425 3015 1875 3015 2100 2625 1875 2235 1425 2235 - 1200 2625 + 3000 2435 2850 2175 2550 2175 2400 2435 2550 2695 2850 2695 + 3000 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3375 2700 2700 -6 -6 4800 3375 5700 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 5025 5250 4050 +6 2400 3075 3000 4200 2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 3825 5025 4215 5475 4215 5700 3825 5475 3435 5025 3435 - 4800 3825 + 3000 3335 2850 3075 2550 3075 2400 3335 2550 3595 2850 3595 + 3000 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 -6 -6 75 2850 1650 5775 -4 0 0 50 -1 0 22 0.0000 2 315 930 75 3150 Ready\001 -4 0 0 50 -1 0 22 0.0000 2 240 1170 75 3525 Threads\001 -4 0 0 50 -1 0 22 0.0000 2 315 1470 150 5700 of Queues\001 -4 0 0 50 -1 0 22 0.0000 2 315 840 150 5325 Array\001 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 -6 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 1200 4500 8700 4500 8700 5400 1200 5400 1200 4500 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 2100 4500 2100 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3000 4500 3000 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3900 4500 3900 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 4500 4800 5325 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 5250 4800 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 5700 4500 5700 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 6600 4500 6600 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 7500 4500 7500 5400 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 2100 6300 1650 5475 + 1 1 1.00 45.00 90.00 + 4500 5700 3450 5400 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 2100 6300 2400 5925 + 1 1 1.00 45.00 90.00 + 4500 5700 5850 5400 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 3000 7200 2100 6375 + 1 1 1.00 45.00 90.00 + 3000 5100 2700 4575 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 3000 7200 3675 6600 + 1 1 1.00 45.00 90.00 + 3000 5100 3300 4800 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 4800 8025 3000 7275 + 1 1 1.00 45.00 90.00 + 3450 5400 3000 5100 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 4875 8025 6600 7275 + 1 1 1.00 45.00 90.00 + 3450 5400 3900 5100 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 6600 7200 5700 6375 + 1 1 1.00 45.00 90.00 + 5400 5100 5100 4575 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 6600 7200 7200 6675 + 1 1 1.00 45.00 90.00 + 5400 5100 5700 4800 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 5700 6300 5250 5475 + 1 1 1.00 45.00 90.00 + 5850 5400 5400 5100 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 - 1 1 1.00 60.00 120.00 - 5700 6300 6000 5925 -4 0 0 50 -1 0 22 0.0000 2 45 270 7950 5025 ...\001 -4 0 0 50 -1 0 22 0.0000 2 315 1020 2325 5850 {\\tt X}\001 -4 0 0 50 -1 0 22 0.0000 2 315 1020 5925 5850 {\\tt X}\001 -4 0 0 50 -1 0 22 0.0000 2 315 1020 7125 6600 {\\tt X}\001 -4 0 0 50 -1 0 22 0.0000 2 315 1020 3600 6525 {\\tt X}\001 + 1 1 1.00 45.00 90.00 + 5850 5400 6300 5100 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 825 3075 X\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 3300 4725 X\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 3900 5025 X\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 5700 4725 X\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 6300 5025 X\001 Index: doc/theses/thierry_delisle_PhD/comp_II/img/resize.fig =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/img/resize.fig (revision 289c7d2d08324b12fa247f070f64d4ffc48bcd09) +++ doc/theses/thierry_delisle_PhD/comp_II/img/resize.fig (revision 4a40f695cc241cf2f33832c81c6644b6c5266085) @@ -8,126 +8,116 @@ -2 1200 2 -6 1200 3300 2100 4950 +6 2400 3075 3000 4200 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 3000 3335 2850 3075 2550 3075 2400 3335 2550 3595 2850 3595 + 3000 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 4200 2700 3600 +-6 +6 2400 2175 3000 3375 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 3000 2435 2850 2175 2550 2175 2400 2435 2550 2695 2850 2695 + 3000 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 2700 3375 2700 2700 +-6 +6 3600 2175 4200 3375 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 4200 2435 4050 2175 3750 2175 3600 2435 3750 2695 4050 2695 + 4200 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 3375 3900 2700 +-6 +6 3600 3075 4200 4200 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 4200 3335 4050 3075 3750 3075 3600 3335 3750 3595 4050 3595 + 4200 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 3900 4200 3900 3600 +-6 +6 4200 3075 4800 4200 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 4800 3335 4650 3075 4350 3075 4200 3335 4350 3595 4650 3595 + 4800 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 4500 4200 4500 3600 +-6 +6 4800 3075 5400 4200 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 5400 3335 5250 3075 4950 3075 4800 3335 4950 3595 5250 3595 + 5400 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 4200 5100 3600 +-6 +6 4800 2175 5400 3375 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 5400 2435 5250 2175 4950 2175 4800 2435 4950 2695 5250 2695 + 5400 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 3375 5100 2700 +-6 +6 4800 1275 5400 2475 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 5400 1535 5250 1275 4950 1275 4800 1535 4950 1795 5250 1795 + 5400 1535 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 5100 2475 5100 1800 +-6 +6 6000 2175 6600 3375 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 6600 2435 6450 2175 6150 2175 6000 2435 6150 2695 6450 2695 + 6600 2435 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 3375 6300 2700 +-6 +6 6000 3075 6600 4200 +2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 + 6600 3335 6450 3075 6150 3075 6000 3335 6150 3595 6450 3595 + 6600 3335 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 1.00 45.00 90.00 + 6300 4200 6300 3600 +-6 +6 6750 4125 7050 4275 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6825 4200 20 20 6825 4200 6845 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200 +1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200 +-6 +6 7500 3675 8475 4500 2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 4950 1650 3975 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 3750 1425 4140 1875 4140 2100 3750 1875 3360 1425 3360 - 1200 3750 + 1 1 1.00 45.00 90.00 + 1 1 1.00 45.00 90.00 + 7500 4200 7950 4200 +4 0 0 50 -1 0 12 0.0000 2 135 915 7500 3825 Grows with\001 +4 0 0 50 -1 0 12 0.0000 2 135 840 7500 4050 additional\001 +4 0 0 50 -1 0 12 0.0000 2 135 840 7500 4425 processors\001 -6 -6 1200 2175 2100 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 1650 3825 1650 2850 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 1200 2625 1425 3015 1875 3015 2100 2625 1875 2235 1425 2235 - 1200 2625 --6 -6 3000 3375 3900 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 3450 5025 3450 4050 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 3000 3825 3225 4215 3675 4215 3900 3825 3675 3435 3225 3435 - 3000 3825 --6 -6 4800 3375 5700 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 5025 5250 4050 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 3825 5025 4215 5475 4215 5700 3825 5475 3435 5025 3435 - 4800 3825 --6 -6 6600 3375 7500 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 7050 5025 7050 4050 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 6600 3825 6825 4215 7275 4215 7500 3825 7275 3435 6825 3435 - 6600 3825 --6 -6 4800 2175 5700 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 3825 5250 2850 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 2625 5025 3015 5475 3015 5700 2625 5475 2235 5025 2235 - 4800 2625 --6 -6 3000 2175 3900 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 3450 3825 3450 2850 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 3000 2625 3225 3015 3675 3015 3900 2625 3675 2235 3225 2235 - 3000 2625 --6 -6 4800 975 5700 2625 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 5250 2625 5250 1650 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 4800 1425 5025 1815 5475 1815 5700 1425 5475 1035 5025 1035 - 4800 1425 --6 -6 6600 2175 7500 3825 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 7050 3825 7050 2850 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 6600 2625 6825 3015 7275 3015 7500 2625 7275 2235 6825 2235 - 6600 2625 --6 -6 3900 3375 4800 5025 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 7 1 1.00 60.00 120.00 - 4350 5025 4350 4050 -2 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7 - 3900 3825 4125 4215 4575 4215 4800 3825 4575 3435 4125 3435 - 3900 3825 --6 -6 75 2850 1650 5775 -6 75 2850 1650 5775 -4 0 0 50 -1 0 22 0.0000 2 315 930 75 3150 Ready\001 -4 0 0 50 -1 0 22 0.0000 2 240 1170 75 3525 Threads\001 -4 0 0 50 -1 0 22 0.0000 2 315 1470 150 5700 of Queues\001 -4 0 0 50 -1 0 22 0.0000 2 315 840 150 5325 Array\001 --6 --6 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3000 3900 3000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 3600 3900 3600 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4200 3900 4200 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 4800 3900 4800 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 5400 3900 5400 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6000 3900 6000 4500 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 6600 3900 6600 4500 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 1200 4500 8700 4500 8700 5400 1200 5400 1200 4500 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 2100 4500 2100 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3000 4500 3000 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 3900 4500 3900 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 4500 4800 5325 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 4800 5250 4800 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 5700 4500 5700 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 6600 4500 6600 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 - 7500 4500 7500 5400 -2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2 - 1 1 1.00 60.00 120.00 - 1 1 1.00 60.00 120.00 - 8850 4950 9450 4950 -4 0 0 50 -1 0 22 0.0000 2 45 270 7950 5025 ...\001 -4 0 0 50 -1 0 22 0.0000 2 315 840 8850 5400 Array\001 -4 0 0 50 -1 0 22 0.0000 2 315 2280 7500 5775 may grow with \001 -4 0 0 50 -1 0 22 0.0000 2 315 3075 6600 6150 additional processors\001 + 2400 3900 7200 3900 7200 4500 2400 4500 2400 3900 +4 2 0 50 -1 0 12 0.0000 2 180 660 2100 4200 Array of\001 +4 2 0 50 -1 0 12 0.0000 2 165 600 2100 4425 Queues\001 +4 2 0 50 -1 0 12 0.0000 2 135 645 2100 3075 Threads\001 +4 2 0 50 -1 0 12 0.0000 2 180 525 2100 2850 Ready\001