Changeset 16d397a


Ignore:
Timestamp:
Apr 24, 2022, 10:53:10 PM (2 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, ast-experimental, master, pthread-emulation, qualifiedEnum
Children:
a6e8f64
Parents:
4f7ad4b
git-author:
Peter A. Buhr <pabuhr@…> (04/24/22 22:50:11)
git-committer:
Peter A. Buhr <pabuhr@…> (04/24/22 22:53:10)
Message:

change task to thread

Location:
doc/theses/mubeen_zulfiqar_MMath
Files:
7 deleted
6 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mubeen_zulfiqar_MMath/allocator.tex

    r4f7ad4b r16d397a  
    651651The following API was created to provide interaction between the language runtime and the allocator.
    652652\begin{lstlisting}
    653 void startTask();                       $\C{// KT starts}$
    654 void finishTask();                      $\C{// KT ends}$
     653void startThread();                     $\C{// KT starts}$
     654void finishThread();                    $\C{// KT ends}$
    655655void startup();                         $\C{// when application code starts}$
    656656void shutdown();                        $\C{// when application code ends}$

  • doc/theses/mubeen_zulfiqar_MMath/background.tex

    r4f7ad4b r16d397a  
    1818\end{comment}
    1919
    20 \chapter[Background]{Background\footnote{Part of this chapter draws from similar background work in~\cite{wasik.thesis} with many updates.}}
     20\chapter[Background]{Background\footnote{Part of this chapter draws from similar background work in~\cite{Wasik08} with many updates.}}
    2121
    2222
    … …  
    213213
    214214\paragraph{\newterm{Program-induced false-sharing}} occurs when one thread passes an object sharing a cache line to another thread, and both threads modify the respective objects.
    215 \VRef[Figure]{f:ProgramInducedFalseSharing} shows when Task$_1$ passes Object$_2$ to Task$_2$, a false-sharing situation forms when Task$_1$ modifies Object$_1$ and Task$_2$ modifies Object$_2$.
     215\VRef[Figure]{f:ProgramInducedFalseSharing} shows when Thread$_1$ passes Object$_2$ to Thread$_2$, a false-sharing situation forms when Thread$_1$ modifies Object$_1$ and Thread$_2$ modifies Object$_2$.
    216216Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
    217217
    … …  
    237237
    238238\paragraph{\newterm{Allocator-induced active false-sharing}} occurs when objects are allocated within the same cache line but to different threads.
    239 For example, in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}, each task allocates an object and loads a cache-line of memory into its associated cache.
     239For example, in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}, each thread allocates an object and loads a cache-line of memory into its associated cache.
    240240Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
    241241
    242242\paragraph{\newterm{Allocator-induced passive false-sharing}} is another form of allocator-induced false-sharing caused by program-induced false-sharing.
    243243When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
    244 For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Task$_1$ passes Object$_2$ to Task$_2$, and Task$_2$ subsequently deallocates Object$_2$.
    245 Allocator-induced passive false-sharing occurs when Object$_2$ is reallocated to Task$_2$ while Task$_1$ is still using Object$_1$.
     244For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Thread$_1$ passes Object$_2$ to Thread$_2$, and Thread$_2$ subsequently deallocates Object$_2$.
     245Allocator-induced passive false-sharing occurs when Object$_2$ is reallocated to Thread$_2$ while Thread$_1$ is still using Object$_1$.
    246246
    247247
    … …  
    461461Ownership prevents the classical problem where one thread performs allocations from one heap, passes the object to another thread, and the receiving thread deallocates the object to another heap, hence draining the initial heap of storage.
    462462As well, allocator-induced passive false-sharing is eliminated because returning an object to its owner heap means it can never be allocated to another thread.
    463 For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, the deallocation by Task$_2$ returns Object$_2$ back to Task$_1$'s heap;
    464 hence a subsequent allocation by Task$_2$ cannot return this storage.
    465 The disadvantage of ownership is deallocating to another task's heap so heaps are no longer private and require locks to provide safe concurrent access.
     463For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, the deallocation by Thread$_2$ returns Object$_2$ back to Thread$_1$'s heap;
     464hence a subsequent allocation by Thread$_2$ cannot return this storage.
     465The disadvantage of ownership is deallocating to another thread's heap so heaps are no longer private and require locks to provide safe concurrent access.
    466466
    467467Object ownership can be immediate or delayed, meaning free objects may be batched on a separate free list either by the returning or receiving thread.
    … …  
    472472It is possible for heaps to steal objects rather than return them and reallocating these objects when storage runs out on a heap.
    473473However, stealing can result in passive false-sharing.
    474 For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Task$_2$'s heap initially.
    475 If Task$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
     474For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Thread$_2$'s heap initially.
     475If Thread$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
    476476
    477477
    … …  
    565565
    566566Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
    567 For example, in \VRef[Figure]{f:ContainerFalseSharing1}, a container being used by Task$_1$ changes ownership, through the global heap.
    568 In \VRef[Figure]{f:ContainerFalseSharing2}, when Task$_2$ allocates an object from the newly acquired container it is actively false-sharing even though no objects are passed among threads.
    569 Note, once the object is freed by Task$_1$, no more false sharing can occur until the container changes ownership again.
     567For example, in \VRef[Figure]{f:ContainerFalseSharing1}, a container being used by Thread$_1$ changes ownership, through the global heap.
     568In \VRef[Figure]{f:ContainerFalseSharing2}, when Thread$_2$ allocates an object from the newly acquired container it is actively false-sharing even though no objects are passed among threads.
     569Note, once the object is freed by Thread$_1$, no more false sharing can occur until the container changes ownership again.
    570570To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
    571571One implementation approach that increases the freedom to return a free container to the operating system involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the operating system.
    … …  
    683683For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps (see~\VRef[Figure]{f:HybridPrivatePublicHeap}).
    684684The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
    685 In the hybrid approach, a task first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
    686 Similarly, a task first deallocates an object its private heap, and second to the public heap.
     685In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
     686Similarly, a thread first deallocates an object its private heap, and second to the public heap.
    687687Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
    688688Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.
    689 Finally, when a task frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing task's private heap for delayed ownership, which allows the freeing task to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.
     689Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.
    690690
    691691\begin{figure}
    … …  
    746746\label{s:LockFreeOperations}
    747747
    748 A \newterm{lock-free algorithm} guarantees safe concurrent-access to a data structure, so that at least one thread makes progress, but an individual task has no execution bound and may starve~\cite[pp.~745--746]{Herlihy93}.
     748A \newterm{lock-free algorithm} guarantees safe concurrent-access to a data structure, so that at least one thread makes progress, but an individual thread has no execution bound and may starve~\cite[pp.~745--746]{Herlihy93}.
    749749(A \newterm{wait-free algorithm} puts a bound on the number of steps any thread takes to complete an operation to prevent starvation.)
    750750Lock-free operations can be used in an allocator to reduce or eliminate the use of locks.
    … …  
    759759
    760760
    761 \subsubsection{Speed Workload}
    762 The worload method uses the opposite approach. It calls the allocator's routines for a specific amount of time and measures how much work was done during that time. Then, similar to the time method, it divides the time by the workload done during that time and calculates the average time taken by the allocator's routine.
    763 *** FIX ME: Insert a figure of above benchmark with description
    764 
    765 \paragraph{Knobs}
    766 *** FIX ME: Insert Knobs
     761% \subsubsection{Speed Workload}
     762% The worload method uses the opposite approach. It calls the allocator's routines for a specific amount of time and measures how much work was done during that time. Then, similar to the time method, it divides the time by the workload done during that time and calculates the average time taken by the allocator's routine.
     763% *** FIX ME: Insert a figure of above benchmark with description
     764%
     765% \paragraph{Knobs}
     766% *** FIX ME: Insert Knobs

  • doc/theses/mubeen_zulfiqar_MMath/figures/AllocInducedActiveFalseSharing.fig

    r4f7ad4b r16d397a  
    1 #FIG 3.2  Produced by xfig version 3.2.5
     1#FIG 3.2  Produced by xfig version 3.2.7b
    22Landscape
    33Center
    44Inches
    5 Letter 
     5Letter
    66100.00
    77Single
    88-2
    991200 2
    10 6 2250 2400 4050 2700
     106 2550 2700 4350 3000
    11112 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    12          2250 2400 3150 2400 3150 2700 2250 2700 2250 2400
     12         2550 2700 3450 2700 3450 3000 2550 3000 2550 2700
    13132 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    14          3150 2400 4050 2400 4050 2700 3150 2700 3150 2400
    15 4 1 0 50 -1 0 11 0.0000 2 195 870 2700 2625 Object$_1$\001
    16 4 1 0 50 -1 0 11 0.0000 2 195 870 3600 2625 Object$_2$\001
     14         3450 2700 4350 2700 4350 3000 3450 3000 3450 2700
     154 1 0 50 -1 0 11 0.0000 2 165 825 3000 2925 Object$_1$\001
     164 1 0 50 -1 0 11 0.0000 2 165 825 3900 2925 Object$_2$\001
    1717-6
    18182 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    19          1050 1500 1950 1500 1950 1800 1050 1800 1050 1500
     19         1350 1800 2250 1800 2250 2100 1350 2100 1350 1800
    20202 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    21          900 900 3000 900 3000 1950 900 1950 900 900
     21         1200 1200 3300 1200 3300 2250 1200 2250 1200 1200
    22222 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    2323        1 1 1.00 45.00 90.00
    24          1950 1950 2700 2400
     24         2250 2250 3000 2700
    25252 2 0 1 0 7 60 -1 -1 0.000 0 0 -1 0 0 5
    26          1950 1500 2850 1500 2850 1800 1950 1800 1950 1500
     26         2250 1800 3150 1800 3150 2100 2250 2100 2250 1800
    27272 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    28          4350 1500 5250 1500 5250 1800 4350 1800 4350 1500
     28         4650 1800 5550 1800 5550 2100 4650 2100 4650 1800
    29292 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    30          3300 900 5400 900 5400 1950 3300 1950 3300 900
     30         3600 1200 5700 1200 5700 2250 3600 2250 3600 1200
    31312 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    3232        1 1 1.00 45.00 90.00
    33          4350 1950 3600 2400
     33         4650 2250 3900 2700
    34342 2 0 1 0 7 60 -1 -1 0.000 0 0 -1 0 0 5
    35          3450 1500 4350 1500 4350 1800 3450 1800 3450 1500
     35         3750 1800 4650 1800 4650 2100 3750 2100 3750 1800
    36362 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    37          2850 1200 2850 975 2250 975 2250 1200 2850 1200
     37         3225 1500 2475 1500 2475 1275 3225 1275 3225 1500
    38382 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    39          5250 1200 5250 975 4650 975 4650 1200 5250 1200
    40 4 1 0 50 -1 0 11 0.0000 2 195 735 2550 1125 Task$_1$\001
    41 4 0 0 50 -1 0 11 0.0000 2 195 720 975 1125 CPU$_1$\001
    42 4 1 0 50 -1 0 11 0.0000 2 135 480 1950 1425 Cache\001
    43 4 1 0 50 -1 0 11 0.0000 2 195 870 1500 1725 Object$_1$\001
    44 4 1 0 50 -1 0 11 0.0000 2 195 870 2400 1725 Object$_2$\001
    45 4 2 0 50 -1 2 11 0.0000 2 135 585 2250 2250 1. alloc\001
    46 4 1 0 50 -1 0 11 0.0000 2 195 735 4950 1125 Task$_2$\001
    47 4 0 0 50 -1 0 11 0.0000 2 195 720 3375 1125 CPU$_2$\001
    48 4 1 0 50 -1 0 11 0.0000 2 195 870 3900 1725 Object$_1$\001
    49 4 1 0 50 -1 0 11 0.0000 2 195 870 4800 1725 Object$_2$\001
    50 4 1 0 50 -1 0 11 0.0000 2 135 480 4350 1425 Cache\001
    51 4 2 0 50 -1 0 11 0.0000 2 180 630 2175 2625 Memory\001
    52 4 0 0 50 -1 2 11 0.0000 2 180 720 4050 2250 4. modify\001
    53 4 2 0 50 -1 2 11 0.0000 2 135 585 3900 2175 3. alloc\001
    54 4 0 0 50 -1 2 11 0.0000 2 180 720 2400 2175 2. modify\001
     39         5625 1500 4875 1500 4875 1275 5625 1275 5625 1500
     404 1 0 50 -1 0 11 0.0000 2 165 855 2850 1425 Thread$_1$\001
     414 0 0 50 -1 0 11 0.0000 2 165 720 1275 1425 CPU$_1$\001
     424 1 0 50 -1 0 11 0.0000 2 135 435 2250 1725 Cache\001
     434 1 0 50 -1 0 11 0.0000 2 165 825 1800 2025 Object$_1$\001
     444 1 0 50 -1 0 11 0.0000 2 165 825 2700 2025 Object$_2$\001
     454 2 0 50 -1 2 11 0.0000 2 135 525 2550 2550 1. alloc\001
     464 1 0 50 -1 0 11 0.0000 2 165 855 5250 1425 Thread$_2$\001
     474 0 0 50 -1 0 11 0.0000 2 165 720 3675 1425 CPU$_2$\001
     484 1 0 50 -1 0 11 0.0000 2 165 825 4200 2025 Object$_1$\001
     494 1 0 50 -1 0 11 0.0000 2 165 825 5100 2025 Object$_2$\001
     504 1 0 50 -1 0 11 0.0000 2 135 435 4650 1725 Cache\001
     514 2 0 50 -1 0 11 0.0000 2 165 615 2475 2925 Memory\001
     524 0 0 50 -1 2 11 0.0000 2 180 720 4350 2550 4. modify\001
     534 2 0 50 -1 2 11 0.0000 2 135 525 4200 2475 3. alloc\001
     544 0 0 50 -1 2 11 0.0000 2 180 720 2700 2475 2. modify\001

  • doc/theses/mubeen_zulfiqar_MMath/figures/AllocInducedPassiveFalseSharing.fig

    r4f7ad4b r16d397a  
    1 #FIG 3.2  Produced by xfig version 3.2.5
     1#FIG 3.2  Produced by xfig version 3.2.7b
    22Landscape
    33Center
    44Inches
    5 Letter 
     5Letter
    66100.00
    77Single
    88-2
    991200 2
    10 5 1 0 1 0 7 50 -1 -1 0.000 0 0 1 0 3750.000 4062.500 2550 975 3750 750 4950 975
     105 1 0 1 0 7 50 -1 -1 0.000 0 0 1 0 4050.000 4662.500 2850 1575 4050 1350 5250 1575
    1111        1 1 1.00 45.00 90.00
    12 6 2250 2400 4050 2700
     126 2550 3000 4350 3300
    13132 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    14          2250 2400 3150 2400 3150 2700 2250 2700 2250 2400
     14         2550 3000 3450 3000 3450 3300 2550 3300 2550 3000
    15152 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    16          3150 2400 4050 2400 4050 2700 3150 2700 3150 2400
    17 4 1 0 50 -1 0 11 0.0000 2 195 870 2700 2625 Object$_1$\001
    18 4 1 0 50 -1 0 11 0.0000 2 195 870 3600 2625 Object$_2$\001
     16         3450 3000 4350 3000 4350 3300 3450 3300 3450 3000
     174 1 0 50 -1 0 11 0.0000 2 165 825 3000 3225 Object$_1$\001
     184 1 0 50 -1 0 11 0.0000 2 165 825 3900 3225 Object$_2$\001
    1919-6
    20202 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    21          1050 1500 1950 1500 1950 1800 1050 1800 1050 1500
     21         1350 2100 2250 2100 2250 2400 1350 2400 1350 2100
    22222 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    23          900 900 3000 900 3000 1950 900 1950 900 900
     23         1200 1500 3300 1500 3300 2550 1200 2550 1200 1500
    24242 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    2525        1 1 1.00 45.00 90.00
    26          1950 1950 2700 2400
     26         2250 2550 3000 3000
    27272 2 0 1 0 7 60 -1 -1 0.000 0 0 -1 0 0 5
    28          1950 1500 2850 1500 2850 1800 1950 1800 1950 1500
     28         2250 2100 3150 2100 3150 2400 2250 2400 2250 2100
    29292 2 0 1 0 7 60 -1 -1 0.000 0 0 -1 0 0 5
    30          3450 1500 4350 1500 4350 1800 3450 1800 3450 1500
     30         3750 2100 4650 2100 4650 2400 3750 2400 3750 2100
    31312 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    32          4350 1500 5250 1500 5250 1800 4350 1800 4350 1500
     32         4650 2100 5550 2100 5550 2400 4650 2400 4650 2100
    33332 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    34          3300 900 5400 900 5400 1950 3300 1950 3300 900
     34         3600 1500 5700 1500 5700 2550 3600 2550 3600 1500
    35352 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    3636        1 1 1.00 45.00 90.00
    37          4350 1950 3600 2400
     37         4650 2550 3900 3000
    38382 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    39          5250 1200 5250 975 4650 975 4650 1200 5250 1200
     39         3225 1800 2475 1800 2475 1575 3225 1575 3225 1800
    40402 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    41          2850 1200 2850 975 2250 975 2250 1200 2850 1200
    42 4 1 0 50 -1 0 11 0.0000 2 195 735 2550 1125 Task$_1$\001
    43 4 0 0 50 -1 0 11 0.0000 2 195 720 975 1125 CPU$_1$\001
    44 4 1 0 50 -1 0 11 0.0000 2 135 480 1950 1425 Cache\001
    45 4 1 0 50 -1 0 11 0.0000 2 195 870 1500 1725 Object$_1$\001
    46 4 1 0 50 -1 0 11 0.0000 2 195 870 2400 1725 Object$_2$\001
    47 4 1 0 50 -1 0 11 0.0000 2 195 735 4950 1125 Task$_2$\001
    48 4 0 0 50 -1 0 11 0.0000 2 195 720 3375 1125 CPU$_2$\001
    49 4 1 0 50 -1 0 11 0.0000 2 195 870 3900 1725 Object$_1$\001
    50 4 1 0 50 -1 0 11 0.0000 2 195 870 4800 1725 Object$_2$\001
    51 4 1 0 50 -1 0 11 0.0000 2 135 480 4350 1425 Cache\001
    52 4 0 0 50 -1 2 11 0.0000 2 180 720 4050 2250 6. modify\001
    53 4 2 0 50 -1 0 11 0.0000 2 180 630 2175 2625 Memory\001
    54 4 2 0 50 -1 2 11 0.0000 2 135 585 2250 2250 1. alloc\001
    55 4 0 0 50 -1 2 11 0.0000 2 180 720 2400 2175 3. modify\001
    56 4 2 0 50 -1 2 11 0.0000 2 135 585 3675 2325 5. alloc\001
    57 4 2 0 50 -1 2 11 0.0000 2 135 780 3975 2175 4. dealloc\001
    58 4 1 0 50 -1 2 11 0.0000 2 195 2400 3750 675 2.  pass Object$_2$ reference\001
     41         5625 1800 4875 1800 4875 1575 5625 1575 5625 1800
     424 1 0 50 -1 0 11 0.0000 2 165 855 2850 1725 Thread$_1$\001
     434 0 0 50 -1 0 11 0.0000 2 165 720 1275 1725 CPU$_1$\001
     444 1 0 50 -1 0 11 0.0000 2 135 435 2250 2025 Cache\001
     454 1 0 50 -1 0 11 0.0000 2 165 825 1800 2325 Object$_1$\001
     464 1 0 50 -1 0 11 0.0000 2 165 825 2700 2325 Object$_2$\001
     474 1 0 50 -1 0 11 0.0000 2 165 855 5250 1725 Thread$_2$\001
     484 0 0 50 -1 0 11 0.0000 2 165 720 3675 1725 CPU$_2$\001
     494 1 0 50 -1 0 11 0.0000 2 165 825 4200 2325 Object$_1$\001
     504 1 0 50 -1 0 11 0.0000 2 165 825 5100 2325 Object$_2$\001
     514 1 0 50 -1 0 11 0.0000 2 135 435 4650 2025 Cache\001
     524 0 0 50 -1 2 11 0.0000 2 180 720 4350 2850 6. modify\001
     534 2 0 50 -1 0 11 0.0000 2 165 615 2475 3225 Memory\001
     544 2 0 50 -1 2 11 0.0000 2 135 525 2550 2850 1. alloc\001
     554 0 0 50 -1 2 11 0.0000 2 180 720 2700 2775 3. modify\001
     564 2 0 50 -1 2 11 0.0000 2 135 525 3975 2925 5. alloc\001
     574 2 0 50 -1 2 11 0.0000 2 135 705 4275 2775 4. dealloc\001
     584 1 0 50 -1 2 11 0.0000 2 165 2220 4050 1275 2.  pass Object$_2$ reference\001

  • doc/theses/mubeen_zulfiqar_MMath/figures/ProgramFalseSharing.fig

    r4f7ad4b r16d397a  
    1 #FIG 3.2  Produced by xfig version 3.2.5
     1#FIG 3.2  Produced by xfig version 3.2.7b
    22Landscape
    33Center
    44Inches
    5 Letter 
     5Letter
    66100.00
    77Single
    … …  
    15152 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    1616         3450 3000 4350 3000 4350 3300 3450 3300 3450 3000
    17 4 1 0 50 -1 0 11 0.0000 2 195 870 3000 3225 Object$_1$\001
    18 4 1 0 50 -1 0 11 0.0000 2 195 870 3900 3225 Object$_2$\001
     174 1 0 50 -1 0 11 0.0000 2 165 825 3000 3225 Object$_1$\001
     184 1 0 50 -1 0 11 0.0000 2 165 825 3900 3225 Object$_2$\001
    1919-6
    20202 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    … …  
    3737         4650 2550 3900 3000
    38382 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    39          3150 1800 3150 1575 2550 1575 2550 1800 3150 1800
     39         5625 1800 5625 1575 4875 1575 4875 1800 5625 1800
    40402 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    41          5550 1800 5550 1575 4950 1575 4950 1800 5550 1800
    42 4 1 0 50 -1 0 11 0.0000 2 195 735 2850 1725 Task$_1$\001
    43 4 0 0 50 -1 0 11 0.0000 2 195 720 1275 1725 CPU$_1$\001
    44 4 1 0 50 -1 0 11 0.0000 2 135 480 2250 2025 Cache\001
    45 4 1 0 50 -1 0 11 0.0000 2 195 870 1800 2325 Object$_1$\001
    46 4 1 0 50 -1 0 11 0.0000 2 195 870 2700 2325 Object$_2$\001
    47 4 1 0 50 -1 0 11 0.0000 2 195 735 5250 1725 Task$_2$\001
    48 4 0 0 50 -1 0 11 0.0000 2 195 720 3675 1725 CPU$_2$\001
    49 4 1 0 50 -1 0 11 0.0000 2 195 870 4200 2325 Object$_1$\001
    50 4 1 0 50 -1 0 11 0.0000 2 195 870 5100 2325 Object$_2$\001
    51 4 1 0 50 -1 0 11 0.0000 2 135 480 4650 2025 Cache\001
    52 4 2 0 50 -1 0 11 0.0000 2 180 630 2475 3225 Memory\001
    53 4 2 0 50 -1 2 11 0.0000 2 135 585 2550 2850 1. alloc\001
     41         3225 1800 3225 1575 2475 1575 2475 1800 3225 1800
     424 1 0 50 -1 0 11 0.0000 2 165 855 2850 1725 Thread$_1$\001
     434 0 0 50 -1 0 11 0.0000 2 165 720 1275 1725 CPU$_1$\001
     444 1 0 50 -1 0 11 0.0000 2 135 435 2250 2025 Cache\001
     454 1 0 50 -1 0 11 0.0000 2 165 825 1800 2325 Object$_1$\001
     464 1 0 50 -1 0 11 0.0000 2 165 825 2700 2325 Object$_2$\001
     474 1 0 50 -1 0 11 0.0000 2 165 855 5250 1725 Thread$_2$\001
     484 0 0 50 -1 0 11 0.0000 2 165 720 3675 1725 CPU$_2$\001
     494 1 0 50 -1 0 11 0.0000 2 165 825 4200 2325 Object$_1$\001
     504 1 0 50 -1 0 11 0.0000 2 165 825 5100 2325 Object$_2$\001
     514 1 0 50 -1 0 11 0.0000 2 135 435 4650 2025 Cache\001
     524 2 0 50 -1 0 11 0.0000 2 165 615 2475 3225 Memory\001
     534 2 0 50 -1 2 11 0.0000 2 135 525 2550 2850 1. alloc\001
    54544 0 0 50 -1 2 11 0.0000 2 180 720 2700 2775 3. modify\001
    55554 0 0 50 -1 2 11 0.0000 2 180 720 4350 2850 4. modify\001
    56 4 1 0 50 -1 2 11 0.0000 2 195 2400 4050 1275 2.  pass Object$_2$ reference\001
     564 1 0 50 -1 2 11 0.0000 2 165 2220 4050 1275 2.  pass Object$_2$ reference\001

  • doc/theses/mubeen_zulfiqar_MMath/pictures/PrivatePublicHeaps.fig

    r4f7ad4b r16d397a  
    1 #FIG 3.2  Produced by xfig version 3.2.5
     1#FIG 3.2  Produced by xfig version 3.2.7b
    22Landscape
    33Center
    44Inches
    5 Letter 
     5Letter
    66100.00
    77Single
    88-2
    991200 2
    10 6 1200 1200 2400 1500
    11 6 1200 1275 2400 1500
    12 4 2 0 50 -1 0 11 0.0000 2 180 915 2250 1425 Public Heap\001
    13 4 0 0 50 -1 0 9 0.0000 2 105 75 2275 1475 1\001
    14 -6
     106 2550 1200 3750 1500
    15112 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    16          1200 1200 2400 1200 2400 1500 1200 1500 1200 1200
    17 -6
    18 6 3900 1200 5100 1500
    19 6 3900 1275 5100 1500
    20 4 0 0 50 -1 0 9 0.0000 2 105 75 4975 1475 2\001
    21 4 2 0 50 -1 0 11 0.0000 2 180 915 4950 1425 Public Heap\001
    22 -6
    23 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    24          3900 1200 5100 1200 5100 1500 3900 1500 3900 1200
    25 -6
    26 6 1425 2100 2700 2400
    27 6 1425 2175 2550 2400
    28 4 2 0 50 -1 0 11 0.0000 2 180 990 2550 2325 Private Heap\001
    29 -6
    30 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    31          1500 2100 2700 2100 2700 2400 1500 2400 1500 2100
    32 4 0 0 50 -1 0 9 0.0000 2 105 75 2575 2375 1\001
    33 -6
    34 6 3525 2100 4800 2400
    35 6 3525 2175 4650 2400
    36 4 2 0 50 -1 0 11 0.0000 2 180 990 4650 2325 Private Heap\001
    37 -6
    38 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    39          3600 2100 4800 2100 4800 2400 3600 2400 3600 2100
    40 4 0 0 50 -1 0 9 0.0000 2 105 75 4675 2375 2\001
    41 -6
    42 6 2550 600 3750 900
    43 2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
    44          2550 600 3750 600 3750 900 2550 900 2550 600
    45 4 1 0 50 -1 0 11 0.0000 2 180 945 3150 825 Global Heap\001
    46 -6
    47 6 1575 3075 2100 3300
    48 4 2 0 50 -1 0 11 0.0000 2 135 375 1950 3225 Task\001
    49 4 0 0 50 -1 0 9 0.0000 2 105 75 1975 3275 1\001
    50 -6
    51 6 4275 3075 4800 3300
    52 4 2 0 50 -1 0 11 0.0000 2 135 375 4650 3225 Task\001
    53 4 0 0 50 -1 0 9 0.0000 2 105 75 4675 3275 2\001
     12         2550 1200 3750 1200 3750 1500 2550 1500 2550 1200
     134 1 0 50 -1 0 11 0.0000 2 180 900 3150 1425 Global Heap\001
    5414-6
    55152 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    5616        1 1 1.00 45.00 90.00
    57          1275 1500 1275 3000
     17         1275 2100 1275 3600
    58182 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    5919        1 1 1.00 45.00 90.00
    60          5025 1500 5025 3000
     20         5025 2100 5025 3600
    61212 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6222        1 1 1.00 45.00 90.00
    63          4650 3000 4650 2400
     23         4650 3600 4650 3000
    64242 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6525        1 1 1.00 45.00 90.00
    66          3975 3075 2400 1500
     26         3975 3675 2400 2100
    67272 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    6828        1 1 1.00 45.00 90.00
    69          2325 3075 3900 1500
     29         2325 3675 3900 2100
    70302 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7131        1 1 1.00 45.00 90.00
    7232        1 1 1.00 45.00 90.00
    73          1950 1200 2550 900
     33         1950 1800 2550 1500
    74342 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7535        1 1 1.00 45.00 90.00
    7636        1 1 1.00 45.00 90.00
    77          3750 900 4350 1200
     37         3750 1500 4350 1800
    78382 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    7939        1 1 1.00 45.00 90.00
    8040        1 1 1.00 45.00 90.00
    81          2550 2100 2550 900
     41         2550 2700 2550 1500
    82422 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
    8343        1 1 1.00 45.00 90.00
    8444        1 1 1.00 45.00 90.00
    85          3750 2100 3750 900
     45         3750 2700 3750 1500
    86462 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
    8747        1 1 1.00 45.00 90.00
    88          4650 2100 4650 1500
     48         4650 2700 4650 2100
    89492 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    9050        1 1 1.00 45.00 90.00
    91          1650 2400 1650 3000
     51         1650 3000 1650 3600
    92522 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
    9353        1 1 1.00 45.00 90.00
    94          1650 2100 1650 1500
     54         1650 2700 1650 2100
    95552 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    9656        1 1 1.00 45.00 90.00
    97          2025 3000 2025 2400
     57         2025 3600 2025 3000
    98582 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
    9959        1 1 1.00 45.00 90.00
    100          4275 2400 4275 3000
     60         4275 3000 4275 3600
    101612 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    102          2325 3300 2325 3000 1200 3000 1200 3300 2325 3300
     62         5100 3900 5100 3600 3975 3600 3975 3900 5100 3900
    103632 4 0 1 0 7 50 -1 -1 0.000 0 0 7 0 0 5
    104          5100 3300 5100 3000 3975 3000 3975 3300 5100 3300
    105 4 1 0 50 -1 0 11 0.0000 2 180 540 3150 1425 locking\001
    106 4 1 0 50 -1 0 11 1.5708 2 135 360 1200 2250 alloc\001
    107 4 1 0 50 -1 0 11 4.7124 2 135 540 4725 2700 dealloc\001
    108 4 1 0 50 -1 0 11 4.7124 2 135 360 5100 2250 alloc\001
    109 4 1 0 50 -1 0 11 5.4803 2 135 540 3375 2775 dealloc\001
    110 4 1 0 50 -1 0 11 0.8029 2 180 780 2700 2625 ownership\001
    111 4 1 0 50 -1 0 11 0.8029 2 135 540 2925 2775 dealloc\001
    112 4 1 0 50 -1 0 11 5.4803 2 180 780 3600 2625 ownership\001
    113 4 1 0 50 -1 0 11 4.7124 2 135 540 4725 1800 dealloc\001
    114 4 1 0 50 -1 0 11 1.5708 2 135 540 1575 2700 dealloc\001
    115 4 1 0 50 -1 0 11 1.5708 2 135 540 1575 1800 dealloc\001
    116 4 1 0 50 -1 0 11 1.5708 2 135 360 1950 2700 alloc\001
    117 4 1 0 50 -1 0 11 4.7124 2 135 360 4350 2700 alloc\001
     64         2325 3900 2325 3600 1200 3600 1200 3900 2325 3900
     652 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
     66         1500 2700 2700 2700 2700 3000 1500 3000 1500 2700
     672 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
     68         1200 1800 2400 1800 2400 2100 1200 2100 1200 1800
     692 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
     70         3900 1800 5100 1800 5100 2100 3900 2100 3900 1800
     712 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
     72         3600 2700 4800 2700 4800 3000 3600 3000 3600 2700
     734 1 0 50 -1 0 11 0.0000 2 180 525 3150 2025 locking\001
     744 1 0 50 -1 0 11 1.5708 2 120 330 1200 2850 alloc\001
     754 1 0 50 -1 0 11 4.7124 2 135 495 4725 3300 dealloc\001
     764 1 0 50 -1 0 11 4.7124 2 120 330 5100 2850 alloc\001
     774 1 0 50 -1 0 11 5.4803 2 135 495 3375 3375 dealloc\001
     784 1 0 50 -1 0 11 0.8029 2 180 750 2700 3225 ownership\001
     794 1 0 50 -1 0 11 0.8029 2 135 495 2925 3375 dealloc\001
     804 1 0 50 -1 0 11 5.4803 2 180 750 3600 3225 ownership\001
     814 1 0 50 -1 0 11 4.7124 2 135 495 4725 2400 dealloc\001
     824 1 0 50 -1 0 11 1.5708 2 135 495 1575 3300 dealloc\001
     834 1 0 50 -1 0 11 1.5708 2 135 495 1575 2400 dealloc\001
     844 1 0 50 -1 0 11 1.5708 2 120 330 1950 3300 alloc\001
     854 1 0 50 -1 0 11 4.7124 2 120 330 4350 3300 alloc\001
     864 1 0 50 -1 0 11 0.0000 2 165 855 1800 3825 Thread$_1$\001
     874 1 0 50 -1 0 11 0.0000 2 165 855 4500 3825 Thread$_2$\001
     884 1 0 50 -1 0 11 0.0000 2 180 1230 1800 2025 Public Heap$_1$\001
     894 1 0 50 -1 0 11 0.0000 2 180 1275 2100 2925 Private Heap$_1$\001
     904 1 0 50 -1 0 11 0.0000 2 180 1230 4500 2025 Public Heap$_2$\001
     914 1 0 50 -1 0 11 0.0000 2 180 1275 4200 2925 Private Heap$_2$\001
Note: See TracChangeset for help on using the changeset viewer.