1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
<!DOCTYPE html
PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- saved from url=(0014)about:internet -->
<html xmlns:MSHelp="http://www.microsoft.com/MSHelp/" lang="en-us" xml:lang="en-us"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="DC.Type" content="topic">
<meta name="DC.Title" content="Appendix A Costs of Time Slicing">
<meta name="DC.subject" content="Appendix A Costs of Time Slicing">
<meta name="keywords" content="Appendix A Costs of Time Slicing">
<meta name="DC.Relation" scheme="URI" content="../tbb_userguide/title.htm">
<meta name="DC.Format" content="XHTML">
<meta name="DC.Identifier" content="tutorial_appendix_A">
<link rel="stylesheet" type="text/css" href="../intel_css_styles.css">
<title>Appendix A Costs of Time Slicing</title>
<xml>
<MSHelp:Attr Name="DocSet" Value="Intel"></MSHelp:Attr>
<MSHelp:Attr Name="Locale" Value="kbEnglish"></MSHelp:Attr>
<MSHelp:Attr Name="TopicType" Value="kbReference"></MSHelp:Attr>
</xml>
</head>
<body id="tutorial_appendix_A">
<!-- ==============(Start:NavScript)================= -->
<script src="..\NavScript.js" language="JavaScript1.2" type="text/javascript"></script>
<script language="JavaScript1.2" type="text/javascript">WriteNavLink(1);</script>
<!-- ==============(End:NavScript)================= -->
<a name="tutorial_appendix_A"><!-- --></a>
<h1 class="topictitle1">Appendix A Costs of Time Slicing</h1>
<div>
<p>Time slicing enables there to be more logical threads than physical
threads. Each logical thread is serviced for a
<em>time slice</em> by a physical thread. If a thread runs longer than a
time slice, as most do, it relinquishes the physical thread until it gets
another turn. This appendix details the costs incurred by time slicing.
</p>
<p>The most obvious is the time for
<em>context switching</em> between logical threads. Each context switch
requires that the processor save all its registers for the previous logical
thread that it was executing, and load its registers for the next logical
thread that it runs.
</p>
<p>A more subtle cost is
<em>cache cooling</em>. Processors keep recently accessed data in cache
memory, which is very fast, but also relatively small compared to main memory.
When the processor runs out of cache memory, it has to evict items from cache
and put them back into main memory. Typically, it chooses the least recently
used items in the cache. (The reality of set-associative caches is a bit more
complicated, but this is not a cache primer.) When a logical thread gets its
time slice, as it references a piece of data for the first time, this data will
be pulled into cache, taking hundreds of cycles. If it is referenced frequently
enough to not be evicted, each subsequent reference will find it in cache, and
only take a few cycles. Such data is called "hot in cache". Time slicing undoes
this, because if a thread A finishes its time slice, and subsequently thread B
runs on the same physical thread, B will tend to evict data that was hot in
cache for A, unless both threads need the data. When thread A gets its next
time slice, it will need to reload evicted data, at the cost of hundreds of
cycles for each cache miss. Or worse yet, the next time slice for thread A may
be on a different physical thread that has a different cache altogether.
</p>
<p>Another cost is
<em>lock preemption.</em> This happens if a thread acquires a lock on a
resource, and its time slice runs out before it releases the lock. No matter
how short a time the thread intended to hold the lock, it is now going to hold
it for at least as long as it takes for its next turn at a time slice to come
up. Any other threads waiting on the lock either pointlessly busy-wait, or lose
the rest of their time slice. The effect is called
<em>convoying</em>, because the threads end up "bumper to bumper" waiting
for the preempted thread in front to resume driving.
</p>
</div>
<div class="familylinks">
<div class="parentlink"><strong>Parent topic:</strong> <a href="../tbb_userguide/title.htm">Intel® Threading Building Blocks (Intel® TBB) User Guide</a></div>
</div>
<div></div>
</body>
</html>
|
