626e682182bfab56cf4b1f7bb45a7ec525970253
[barrelfish] / doc / 005-scc / SCC.tex
1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 % Copyright (c) 2011, 2012, ETH Zurich.
3 % All rights reserved.
4 %
5 % This file is distributed under the terms in the attached LICENSE file.
6 % If you do not find this file, copies can be found by writing to:
7 % ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9
10 \documentclass[a4paper,twoside]{report} % for a report (default)
11
12 \usepackage{bftn} % You need this
13 \usepackage{multirow}
14 \usepackage{listings}
15 \usepackage{color}
16
17 \title{Barrelfish on the Intel Single-chip Cloud Computer}   % title of report
18 \author{Simon Peter \and Timothy Roscoe \and Andrew Baumann}    % author
19 \tnnumber{005}  % give the number of the tech report
20 \tnkey{Single-chip Cloud Computer} % Short title, will appear in footer
21
22 % \date{Month Year} % Not needed - will be taken from version history
23
24 \begin{document}
25 \maketitle
26
27 %
28 % Include version history first
29 %
30 \begin{versionhistory}
31 \vhEntry{0.1}{08.02.2010}{SP,TR}{Initial version}
32 \vhEntry{1.0}{20.07.2010}{SP,TR,AB}{Updates, more detail}
33 \vhEntry{1.1}{11.08.2010}{SP}{Fill in missing details}
34 \vhEntry{1.2}{12.08.2010}{TR}{Initial release version}
35 \vhEntry{1.3}{09.09.2010}{SP,RB}{Corrections to typos and for clarity}
36 \vhEntry{1.4}{10.05.2012}{SP}{Fake VGA console removed. Physical
37   memory layout added.}
38 \end{versionhistory}
39
40 % \intro{Abstract}              % Insert abstract here
41 % \intro{Acknowledgements}      % Uncomment (if needed) for acknowledgements
42 % \tableofcontents              % Uncomment (if needed) for final draft
43 % \listoffigures                % Uncomment (if needed) for final draft
44 % \listoftables                 % Uncomment (if needed) for final draft
45
46 \lstset{
47   language=C,
48   basicstyle=\ttfamily \small,
49   flexiblecolumns=false,
50   basewidth={0.5em,0.45em},
51   boxpos=t,
52 }
53
54 \newcommand{\eclipse}{ECL\textsuperscript{i}PS\textsuperscript{e}\xspace}
55 \newcommand{\codesize}{\scriptsize}
56 \newcommand{\note}[1]{[\textcolor{red}{\emph{#1}}]}
57
58 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
59 \chapter{Introduction}
60
61 This report describes the Barrelfish port to the Intel Single-chip
62 Cloud Computer \cite{intel:scc:isscc10}.   It serves as a general
63 repository for information about the SCC platform, and therefore
64 contains a number of very different kinds of information, for
65 different audiences.  It should be regarded as an evolving set of
66 notes, rather than a polished document. 
67
68 \begin{itemize}
69
70 \item Chapter~\ref{chap:impl} describes the SCC-specific aspects of the
71 port. This information is of most interest to people trying to
72 understand the SCC-specific functionality in Barrelfish. 
73
74 \item Chapter~\ref{chap:bench} collects various hardware
75   microbenchmarks which were used to guide the implementation.  This
76   is of interest to those wishing to understand the performance of
77   individual operations on the SCC, for example to optimize the 
78   Barrelfish implementation. 
79
80 \item Chapter~\ref{chap:eval} provides both a quantitative and
81   qualitative evaluation of Barrelfish running on the SCC.  This
82   summarizes our results of running a limited number of applications
83   on Barrelfish using the SCC. 
84
85 \item Chapter~\ref{chap:refl} discusses the implications of our early
86   experience for future system software on the SCC, and provides some
87   thoughts on the suitability of the SCC's hardware for running a
88   message-based OS such as Barrelfish.  This deals primarily with how
89   well-matched the Barrelfish design is with the hardware features of
90   the SCC. 
91
92 \item Chapter~\ref{chap:historical} collects information about
93   historical features of the port that are not supported anymore.
94 \end{itemize}
95
96 The work described in the current version of this document was carried
97 out entirely on the ``Copper Ridge'' SCC platform.  
98 As the Barrelfish project gains more experience with the ``Rocky
99 Lake'' SCC platform, this document will be updated accordingly. 
100
101 We would like
102 thank Intel Corporation, in particular the SCC team and the Intel
103 Braunschweig Lab, for their help and early access to the SCC
104 platform. 
105
106
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
108 \chapter{Barrelfish implementation on SCC}\label{chap:impl}
109
110 This chapter describes the SCC-specific parts of Barrelfish, and how
111 they differ from other target architectures.   The SCC port of
112 Barrelfish is still in its early stages (the version described here is
113 based on less than 10 person-days of access to early SCC hardware), so
114 this should be viewed as a preliminary discussion.  
115
116 The work was carried out by Simon Peter at the Intel Braunschweig lab
117 from the 8th to the 12th March 2010, and subsequently from the 26th to
118 the 30th April 2010. 
119
120 \section{CPU driver}
121
122 All cores in a Barrelfish system run a CPU driver, which is the only
123 code which runs in privileged mode on the core.  
124
125 The SCC CPU driver is based on the x86-32 port of Barrelfish, and is
126 identical to it except for not supporting the various address
127 extensions (PAE, etc.) available on modern 32-bit ia32
128 machines. Instead, kernel-mode support for multiplexing access to
129 message passing buffers (MPBs) and configuration registers is
130 provided.
131
132 The SCC CPU driver also supports the x86 UART for debugging output. A
133 version of the SCC host PC driver\footnote{Available at:
134   \url{http://www.dcl.hpi.uni-potsdam.de/research/scc/serial.htm}}
135 supports a virtual UART for each core on the SCC.
136
137 \section{Compilation}
138
139 A symbolic target \texttt{scc} has been added to the Barrelfish
140 makefile. This target carries out two additional steps necessary to
141 produce a bootable binary image file:
142
143 \begin{enumerate}
144 \item A Barrelfish binary image is compiled from ELF images of the
145   kernel and user-space binaries, together with essential bootup
146   information (like commandline parameters for those binaries and a
147   memory map) from an enhanced GRUB~\cite{grub} \texttt{menu.lst}
148   file. This is done using the \texttt{dite} image generation tool,
149   written at ETH and included in the \texttt{/tools/dite} directory of
150   the Barrelfish source tree. The image is relocated to be loaded at
151   address 0xff000.
152
153 \item This binary image is converted into Intel 32.obj binary format
154   (an Intel-proprietary format) and combined with a 5 byte jump
155   vector, to be loaded at address 0xfffffff0, long jumping to
156   0x100000, the fixed entry point of the kernel.
157
158 \item Another 32.obj file is created, containing only the 5 byte jump
159   vector to the same fixed entry point of the kernel.
160 \end{enumerate}
161
162 \section{Boot process: first (bootstrap) core}
163
164 The \verb+tools/scc/bootscc.sh+ shell script can be used to boot the
165 SCC. This script will invoke the following sccKit tools on the host PC
166 to bootstrap the first SCC core:
167
168 \begin{alltt}
169   sccReset -g
170   sccMerge -m4 -n12 -noimage -lut\_default -force barrelfish48.mt
171   sccBoot -g obj
172   sccReset -r 0
173 \end{alltt}
174
175 The first \texttt{sccReset} will reset the SCC board into a known
176 state, in particular all configuration registers.
177
178 \texttt{sccMerge} creates memory images for all memory controllers
179 from the previously created 32.obj files. It will load the boot image
180 to core 0's memory and load the boot jump vector to all other
181 cores. The default LUT mappings are created for each core. The file
182 \texttt{barrelfish48.mt} provided on the commandline is responsible
183 for this configuration. It is shipped with the Barrelfish source
184 distribution. \texttt{sccMerge} creates an \texttt{obj} subdirectory
185 containing the produced memory images. If the directory already
186 exists, it is removed first.
187
188 \texttt{sccBoot} loads the memory images into the memory controllers
189 from the \texttt{obj} subdirectory.
190
191 The second \texttt{sccReset} will release the reset pin of the first
192 SCC core (core ID 0).
193
194 The kernel boot code switches from real mode to protected mode,
195 activates paging, all caches and the message passing buffers. In
196 addition to the regular x86-32 startup sequence, it initializes the
197 in-kernel SCC support code and reads the core ID from the local core
198 mapping.
199
200 The rest of the local boot process is identical to the x86-32 boot
201 process.
202
203 \section{Boot process: subsequent cores}
204
205 When told to boot another SCC core with a given core ID, the CPU
206 driver will modify the booter's LUT mapping to map in the first 16MB
207 (one LUT entry) of the bootee at a known fixed address, known not to
208 contain useful memory of the booter.
209
210 The booter will then ELF load a copy of the CPU driver to address
211 0x10000 and append copies of the ELF binaries of the CPU driver, the
212 monitor, init, and mem\_serv. These programs are needed to bring up
213 the bootee core. A special configuration region at address 0xff00 is
214 also written to inform the bootee that it is an application kernel,
215 the address of the inter-monitor CC-UMP message passing region in
216 shared RAM, the location of the binary copies, as well as the
217 notification channel ID used for that channel. CC-UMP and notification
218 channels are described in Section~\ref{sec:interconnect}.  Then, the
219 reset pin of the bootee is released via configuration registers.
220
221 \section{Physical address space}
222
223 The SCC allows the physical address space of each core to be
224 configured using the 256-entry Lookup Table~\cite{rockcreek_eas}
225 (LUT).  In normal operation, we use the default LUT memory map, as is
226 used by Intel for the Linux OS, and amend it for extra physical memory
227 if available. The memory map is described in the
228 \verb+hake/menu.lst.scc+ file, and inserted into the boot image by the
229 \verb+dite+ tool, where the kernel can find it.
230
231 \begin{center}
232 \begin{tabular}{lll}
233 Area & start & end\\
234 \hline
235 Private DDR3 RAM & 0 & 0x28ffffff \\
236 Remote boot LUT & 0x29000000 & 0x29ffffff \\
237 \emph{Unused} & 0x2a000000 & 0x7fffffff \\
238 Shared DDR3 RAM & 0x80000000 & 0xbfffffff \\
239 On-tile MPBs & 0xc0000000 & 0xd7ffffff \\
240 Local on-tile MPB & 0xd8000000 & 0xd8ffffff \\
241 \emph{Unused} & 0xd9000000 & 0xdfffffff \\
242 Configuration registers & 0xe0000000 & 0xf7ffffff \\
243 Local configuration regs & 0xf8000000 & 0xf8ffffff \\
244 eMAC access & 0xf9000000 & 0xf9ffffff \\
245 TCP/IP traffic (unused) & 0xfa000000 & 0xfaffffff \\
246 RPC (unused) & 0xfb000000 & 0xfbffffff \\
247 SATA (unused) & 0xfc000000 & 0xfcffffff \\
248 \emph{Unused} & 0xfd000000 & 0xfeffffff \\
249 Private DDR3 RAM & 0xff000000 & 0xffffffff \\
250 \end{tabular}
251 \end{center}
252
253 \section{Virtual address space}
254
255 The available virtual address space on a core is split into 2GB
256 user-space access (addresses 0x0 -- 0x7fffffff) and 2GB for
257 kernel-only access (addresses 0x80000000 -- 0xffffffff).
258
259 The kernel-only space maps directly to physical address 0x0 until
260 0x3fffffff, allowing access to all of private RAM with the default LUT
261 mapping. This resembles mappings used in single address space
262 operating systems and provides better performance when handling kernel
263 objects than can be provided with classical operating systems, like
264 Linux. Kernel objects can point to other objects directly and the
265 mapping is identical across all cores. Also, physical addresses can be
266 calculated simply by subtracting an offset, instead of via complicated
267 mappings.
268
269 Space is reserved at the top of this range to map all MPBs and all
270 configuration registers, as well as the local APIC and one remappable
271 4K page to map in a foreign core's private RAM, used for booting that
272 core.  The rest of kernel virtual address space is unused. This
273 implies that kernel objects can only be created in the lower 2GB of
274 physical memory (ie. in private RAM), which is sufficient in
275 Barrelfish, as kernel objects are never shared between cores.
276
277 The user-space address range can be arbitrarily mapped to physical
278 addresses.
279
280 \section{Memory allocation}
281
282 A memory allocation server (\texttt{mem\_serv}) is spawned for every
283 on-line core in the system.
284
285 Available shared RAM is equi-partitioned into 48 regions. Remaining
286 shared RAM not fitting this partition is thrown away and is not
287 usable. The reason for this is that the memory allocators are not able
288 to handle allocation from unaligned memory regions and sizes that are
289 not a power of two.
290
291 The server gets given capabilities for all of the private RAM of the
292 local core and \textbf{all of shared RAM}. This is necessary so that
293 allocation of shared mappings is possible from every core's region
294 without having to contact a designated memory allocator for this
295 region of RAM, a feature not yet implemented.
296
297 As shared RAM is handled identical to private RAM, the kernel is
298 responsible for clearing a newly allocated page of memory from
299 previous usage before allowing it to be mapped into the allocator's
300 address space. As shared RAM resides outside the lower 2GB of physical
301 address space, the kernel is incapable of accessing that RAM in order
302 to clear it. For SCC, we have modified the kernel to instead neglect
303 clearing the page, at the expense of protection when memory is reused
304 from other address spaces.
305
306 This issue is fixable however, either by reserving another remappable
307 address range inside the kernel that can be used to map and clear the
308 page before allowing the user to map it, at an expense of
309 performance. Another way to fix it is to introduce a special memory
310 allocator for shared RAM that would map and clear allocated RAM first
311 into its own address space before granting it to the requesting
312 address space.
313
314 Per-core memory servers are necessary on SCC. Memory servers do not
315 currently support allocation from multiple private RAM regions with
316 overlapping address regions.
317
318 \section{Interconnect driver}\label{sec:interconnect}
319
320 In Barrelfish, an interconnect driver is the lowest-level part of a
321 particular messaging mechanism. The inter-core interconnect driver for
322 the SCC is based on the cache-coherent user-level message passing
323 (CC-UMP) driver used by Barrelfish on x86 systems. With some
324 modifications this mechanism reliably transports cache-line-sized
325 messages through non-coherent shared memory on SCC.
326
327 The modifications are:
328 \begin{itemize}
329 \item The size of a cache-line, and thus message, is 32 bytes.
330
331 \item Memory for both the send and receive message channel is
332   allocated in the core's region of shared RAM that is initiating a
333   bind to another core, using the NUMA allocation features of
334   Barrelfish. These are currently not thread-safe and thus the
335   interconnect driver initialisation phase is currently not
336   thread-safe.
337
338 \item Memory for the message channel is mapped as cacheable, message
339   passing buffer type, enabling the use of the write-combining buffer
340   for faster memory writes. For this, the implementation of the
341   virtual memory manager inside \texttt{libbarrelfish} had to be
342   extended to support the architecture-specific mapping flags.
343 \end{itemize}
344
345 While CC-UMP was originally optimized for cache-coherent transports, these
346 optimizations do not hurt performance on SCC and we are not aware of other
347 SCC-specific optimizations that CC-UMP does not already employ.
348
349 However, the polling approach used by CC-UMP on Barrelfish to detect incoming
350 messages is inappropriate on the SCC, since each poll of a message-passing
351 channel requires a \texttt{CL1INVMB} operation followed by a load from DDR3
352 memory.
353
354 Consequently, an additional SCC notification driver (named
355 \texttt{rck\_notify}) was implemented which augments the CC-UMP driver
356 with notification support. For this, support for pluggable
357 notification drivers was added to CC-UMP.
358
359 The notification driver uses the on-tile MPB for efficiently
360 communicating the identifiers of active message channels, and
361 an inter-core interrupt as the notification mechanism. It is implemented
362 mostly within the CPU driver on each core, as follows: \note{AB: Diagram?}
363
364 \begin{itemize}
365 \item A ring-buffer of IDs of those channels containing unread payload
366   is held in the receiver's MPB. The buffer is written only by senders and
367   read only by the receiver. However, there are two read-shared
368   cache lines before the buffer, holding the current write and current
369   read position, respectively.
370 \item A buffer entry spans a cache-line (32 bytes). Currently, only a
371   16-bit channel ID is written to that cache-line, limiting the number
372   of distinct notifiable channels to 65,536. The rest of the space in
373   unused. Using a cache-line per ID allows a sender to write new
374   channel IDs to the buffer without having to read the cacheline for
375   already existing IDs first.
376 \item A new capability type is used on the sender side, holding the
377   core ID and channel ID of the receiver core of the
378   notification. When invoked, the sender's CPU driver:
379   \begin{enumerate}
380    \item Acquires the test-and-set lock for the receiving core
381    \item Reads the current write position from the receiver's MPB
382    \item Writes the channel ID into the next slot in the reciever's MPB
383    \item Updates the current write position in the receiver's MPB
384    \item Reads the receiver's interrupt status
385    \item If no inter-core interrupt is pending, writes the status word
386          with the interrupt set to trigger a remote interrupt
387    \item Clears the test-and-set lock for the receiving core
388   \end{enumerate}
389 \item On the receiver, a regular LMP endpoint capability is registered
390   in a special notification table inside the CPU driver. This table maps
391   channel IDs to local LMP endpoints that will be signalled on notification.
392   When the receiver core is interrupted, it looks up all pending channel IDs
393   present in the MPB ring-buffer, and dispatches an empty message on the
394   registered endpoint in the table. If no endpoint is registered, an error
395   is signalled.
396 \item In user-space, the notification driver triggers the waitset used
397   to wait on incoming messages for the corresponding message channel,
398   activating the receive message handler in the generated stubs, which
399   are described in the following section.
400 \end{itemize}
401
402 In case of the receiver ring buffer being full when the sender tries
403 to write a new channel ID, the sender aborts the process and returns
404 with an error code to the sending user-space application, indicating a
405 failed notification. The user-space application should try to notify
406 the receiver again at a later point in time (currently unimplemented
407 as we did not reach this case during our benchmarks). Rolling back the
408 message send is not easily possible, as the receiver might have been
409 actively polling for and already reading it.
410
411 Allocation of new channel IDs is managed by the monitor of the
412 receiving core as part of the bind process. The CPU driver does not
413 allocate IDs.
414
415 There are many design alternatives for an SCC interconnect driver, and
416 the above should be regarded as only one point in the space.  At first
417 sight, it may seem odd to use main memory (rather than the on-tile
418 MPB) for passing message payloads, and to require a trap to the kernel
419 to send a message notification.
420
421 This design is motivated by the need to support many message channels
422 in Barrelfish and, furthermore, more than one application running on a
423 core.  The SCC's message-passing functionality does not appear to have
424 been designed with this use-case in mind.
425 We discuss this issue further in Chapter~\ref{chap:refl}. 
426
427 We considered two further design alternatives: \emph{notification
428   trees} and \emph{payload in MPB}. The former we have implemented and
429 benchmarked, but it turned out to have worse performance than the ring
430 buffer implementation presented above.
431
432 Notification trees use the same notification scheme as ring buffers,
433 but employ a bitmap of channel IDs, represented as a two-level tree in
434 the receiver's MPB. One bit for every distinct channel that can be
435 notified. Tree nodes are of the size of one cache-line (256 bits). The
436 tree's layout in the ring buffer is such that the root node occupies
437 the first cache-line. All other nodes are leaves and are stored in
438 left-to-right order after the root node. There are 255 leaves which
439 contain a bit for each notifiable channel, yielding 65,280 notifiable
440 channels. A bit set in the root node indicates that the corresponding
441 leave contains set bits and should be scanned when the tree is
442 traversed. In this scheme, sending a notification can never fail: A
443 bit can either be set or is already set, in which case no further
444 notifications need to be sent for the respective channel ID.
445
446 Sending a notification for a given channel ID in this design requires
447 the sender to:
448
449 \begin{enumerate}
450 \item Acquire the test-and-set lock for the receiving core
451 \item Read the root node from the receiver's MPB
452 \item Set the bit for the corresponding leaf node of the channel ID
453   in the root node
454 \item Write the root node to the receiver's MPB
455 \item Read the leaf node from the receiver's MPB
456 \item Set the bit for the corresponding channel ID in the leaf node
457 \item Write the leaf node to the receiver's MPB
458    \item Read the receiver's interrupt status
459    \item If no inter-core interrupt is pending, write the status word
460      with the interrupt set to trigger a remote interrupt
461 \item Clear the test-and-set lock for the receiving core
462 \end{enumerate}
463
464 This mechanism requires 2 full cache-line reads and 2 full cache-line
465 writes from/to the receiver's MPB and 2 bit operations as opposed to
466 only two 32-bit reads and 2 full cache-line writes in the ring buffer
467 scheme. We originally proposed notification trees, assuming the cost
468 to access remote MPBs would be an order of magnitude lower, as well as
469 cheaper bit operations on full cache-lines. After implementing and
470 benchmarking this scheme, it turned out not to be the case. We assume
471 the slow bit operations to be due to the size of the operands. Holding
472 a full cache-line would require 8 integer registers on the Pentium.
473 With only 7 present, we always have to go to memory in order to
474 execute a bit-scan, an expensive operation, especially when the cache
475 does not allocate on a write miss.
476
477 The final design we devised is ``payload in MPB''. In this scheme,
478 instead of notifying the receiver of a message in shared RAM, the
479 message payload itself is written to the MPB, obliviating the need for
480 shared RAM. The main drawback of this scheme is that it requires quite
481 complicated book-keeping, as messages are variable size and might not
482 fit into the rather small 8KB receive buffer.
483
484 It also complicates managing quality of service, as multiple
485 applications now compete for the same receiver MPB. This forbids
486 receiving applications the use of the payload inside the MPB directly,
487 as the MPB has to be freed up as quickly as possible to allow other
488 competing applications to make progress. This requires copying the
489 message out of the MPB into private RAM of the receiver, which is
490 again a costly operation, especially as caches do not allocate on a
491 write miss. We elaborate more on this issue in
492 Chapter~\ref{chap:refl}.
493
494 \section{Message passing stubs}
495
496 In Barrelfish, message-passing stubs are the next layer of functionality
497 above the interconnect driver, and implement typed variably-sized messages
498 over various interconnects. They are generated by our stub-generation tool,
499 named \emph{Flounder}.
500
501 The Flounder backend for SCC message passing is derived from, and shares much
502 code with, the backend for CC-UMP. The important differences are:
503
504 \begin{itemize}
505 \item The generated stubs are configured for a cache-line size of 32 bytes,
506   and thus the message-fragments used to transmit message payload are never
507   more than 32-bytes in size.
508 \item The binding logic allocates and initialises the SCC notification
509   endpoints, and transmits their capabilities to the receiver.
510 \item The code to send messages is modified to emit a notification either at
511   the end of a complete (application-level) message, or when the message
512   channel ring buffer is full and the sender needs to block. In this way,
513   needless notifications (for fragments of a high-level message) are avoided.
514 \item The receive side never polls for incoming messages. When no more messages
515   are present in the channel, it instead blocks on a waitset that will be
516   signalled when an inter-core notification arrives.
517 \end{itemize}
518
519 \section{Bulk transfer}
520
521 Bulk transfer shared memory is mapped the same way as CC-UMP
522 memory on SCC (cacheable, MPB).  
523
524 As shared memory is directly manipulated by the application for a bulk
525 transfer region, the bulk\_prepare() function for SCC touches a random
526 cacheline that is not of the bulk transfer region. This forces the
527 write combine buffer to flush the last written cacheline out to
528 memory (see Section 1.4.5 of~\cite{rockcreek_core_eas}). This needs
529 to be done, as an application may have written an incomplete cacheline
530 to the transfer area, to force that line out to memory before sending.
531
532 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
533 \chapter{Hardware measurements}\label{chap:bench}
534
535 Cost of assorted local operations: 
536
537 \begin{center}
538 \begin{tabular}{rl}
539 operation & cycles \\
540 \hline \\
541 NOP system call & 200 \\
542 RDTSC instruction & 14 \\
543 XCHG instruction & 35 \\
544 LOCK CMPXCHG instruction & 39 \\
545 LOCK DEC instruction & 36 \\
546 clear memory & 3 \\
547 NOP instruction & 2 \\
548 CL1INVMB & 1 \\
549 \end{tabular}
550 \end{center}
551
552 Cost in cycles to write a complete 32-byte cache line (8 DWORD writes)
553 to an on-tile MPB from a core on tile 0:
554
555 \begin{center}
556 \begin{tabular}{cc|cccccc}
557 &  &\multicolumn{6}{c}{\textit{target tile x-coordinate}} \\
558  &   & 0   & 1   & 2   & 3   & 4   & 5 \\ \hline 
559 \multirow{4}{*}{\textit{y}} & 0 & 39  & 84  & 89  & 90  & 95  & 101 \\
560  & 1 & 84  & 89  & 89  & 95  & 101 & 108 \\
561  & 2 & 89  & 89  & 95 & 101 & 107 & 113 \\
562  & 3 & 89  & 95  & 101 & 108 & 113 & 119 \\
563 \end{tabular}
564 \end{center}
565
566 Cost to read a single DWORD from on-tile MPBs from tile 0 (this will
567 pull the cache line into local L1 on tile 0):
568
569 \begin{center}
570 \begin{tabular}{cc|cccccc}
571 &  &\multicolumn{6}{c}{\textit{source tile x-coordinate}} \\
572  &   & 0   & 1   & 2   & 3   & 4   & 5 \\ \hline 
573 \multirow{4}{*}{\textit{y}} & 0 & 20  & 63  & 69  & 72  & 78  & 84 \\
574  & 1 & 63  & 69  & 72  & 78  & 84  & 90 \\
575  & 2 & 69  & 72  & 78  & 84  & 90  & 96 \\
576  & 3 & 72  & 78  & 84  & 90  & 96  & 102 \\
577 \end{tabular}
578 \end{center}
579
580 \section{Memory map and shared memory areas}
581
582 In this benchmark, a user-space application reads/writes repeatedly
583 from/to shared memory, using different mapping configurations. Core 0
584 executed this benchmark. All numbers presented are in machine cycles.
585
586 \begin{center}
587 \begin{tabular}{cccl}
588 \hspace{3em} & Memory controller & average & total for 1,000,000 iterations \\
589 \hline \\
590 \multicolumn{4}{l}{DWORD from shared RAM (uncacheable):} \\
591 \\
592  & 0 & 97  & 97,338,585 \\
593  & 1 & 121 & 121,492,066 \\
594  & 2 & 105 & 105,348,809 \\
595  & 3 & 134 & 133,690,789 \\
596 \\
597 \multicolumn{4}{l}{Cacheline to shared RAM (uncacheable):} \\
598 \\
599  & 0 & 779 & 778,680,899 \\
600  & 1 & 972 & 971,920,810 \\
601  & 2 & 843 & 842,761,220 \\
602  & 3 & 1069 & 1,069,474,168 \\
603 \\
604 \multicolumn{4}{l}{Cacheline to shared RAM (MPB):} \\
605 \\
606  & 0 & 122 & 121,504,321 \\
607  & 1 & 146 & 146,014,496 \\
608  & 2 & 134 & 133,697,675 \\
609  & 3 & 158 & 157,781,513 \\
610 \end{tabular}
611 \end{center}
612
613 \section{Thread Switch Time}
614
615 In this benchmark two threads are yielding between each  other in a
616 ping-pong like benchmark. Therefore, Barrelfish's
617 thread\_yield\_dispatcher function is used. This function donates the
618 callers time-slice to the dispatcher pointed to by the argument to this
619 function.
620
621 A call to this function requires an endpoint capability to the
622 partner, which needs to be exchanged between the threads at
623 startup. One of the dispatchers acts as a server, calling export to
624 offer the service to the nameserver, the other one as a client calling
625 the bind function.
626
627 The waitloops are broken as soon as both partners have the required
628 endpoint capabilities set up. When looking at the numbers given in
629 this benchmark, it is important to keep in mind that the domains might
630 run some event processing code on scheduling.
631
632 The decision to include those numbers in the measurements is on
633 purpose for this analysis.
634
635 The number of cycles given is from one thread to the partner and back
636 to the original thread and therefore needs to be divided by two to get
637 an approximation for the actual thread switch time.
638
639 \begin{center}
640 \begin{tabular}{rl}
641 thread & cycles \\
642 \hline \\
643 server & 6732.79\\
644 client & 6636.08\\
645 \end{tabular}
646 \end{center}
647
648
649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
650 \chapter{Evaluation of the implementation}\label{chap:eval}
651
652 This chapter describes the effort required to bring up Barrelfish on
653 the SCC, together with early micro- and application benchmark
654 results. 
655
656 \section{Development effort}
657
658 Bringing up Barrelfish on the SCC first required a 32-bit ia32 port,
659 since up to that point we had only targetted 64-bit Intel Archtecture
660 platforms.  This port was carried out in advance by Simon using a
661 mixture of real hardware and QEMU configured to emulate a Pentium
662 processor, and substantially reduced the time required on actual SCC
663 hardware. 
664
665 The process was also helped by Orion Hodson's ARM port, and Richard
666 Black's Beehive port, which threw up many 64-bit dependencies at an
667 early stage.  In the event, most of these issues were resolved well
668 before the SCC port started. 
669
670 Lines of code, using David Wheeler's SLOCCount:
671
672 \begin{itemize}
673 % \item Using SLOCcount on only the x86-32 specific code yields 6108
674 %   lines of C code and 130 lines of assembly code (not counting
675 %   imported code, like libc or libm). Out of this, 70\% is kernel
676 %   code.
677
678 \item As of August 11, 2010, the x86-32 specific code yields 8705
679   lines of C code and 410 lines of assembly code (not counting
680   imported code, like libc or libm). Out of this, 6011 lines (69\%) is
681   kernel (CPU driver) code.
682
683 \item In addition to the x86-32 specific code, 2235 lines of
684   SCC-specific C code and 130 lines of assembly code were written, 391 
685   lines (17\%) of these being CPU driver. This count does not include
686   the sections of x86-32 specific code that have workarounds for SCC
687   using \#ifdef constructs.
688 \end{itemize}
689
690 By and large, the bringup for SCC was straightforward:
691
692
693 \begin{itemize}
694 \item Porting back from x86-64 using a memory-window
695   based model for kernel state allowed us to keep the programming
696   model and general address space layout.  One minor issues was the
697   requirement to initialize shared RAM from
698   user-space.  This makes it unsafe to allow regular user-space
699   applications access to untyped memory, as they could snoop its
700   previous content without erasing the memory.
701
702 \item At the time of the x86-32 port, most arch-generic Barrelfish
703   code was still mostly x86-64-specific and so time was spent on
704   separating out arch-specific quirks from otherwise generic code and
705   clean-up. 
706
707 \item The message passing transport was designed within one
708   day. However, it turned out it was not as efficient as expected, due
709   to our (overly optimistic) assumptions about memory access latencies.
710
711 \item Overall, the work took about 2 person-months.
712 \end{itemize}
713
714 At time of writing, we believe the major performance issues with our
715 code are due to the SCC L2 caches' non-allocate-on-write policy. Our
716 code is not optimized for this behavior and shows major
717 inefficiencies, in particular on function call boundaries immediately after
718 kernel crossings.
719
720 % \section{Measurements}\label{sec:measurements}
721
722 % %    * Breakdown of IPI pingpong benchmark (cores 0 \& 1): 16722
723 % %     * Sender: Into kernel, up to rck\_send\_notification(): 687 cycles
724 % %     * Sender: Time taken for rck\_send\_notification(): 605 cycles
725 % %     * Sender: Upon receipt of message from peer: 7987 cycles
726
727 % %    * cores 0 \& 2: 17372
728 % %     * Sender: Into kernel, up to rck\_send\_notification(): 687 cycles
729 % %     * Sender: Time taken for rck\_send\_notification(): 794 cycles
730 % %     * Sender: Upon receipt of message from peer: 8224 cycles
731
732 % %    * cores 0 \& 10: 17794
733 % %     * Sender: Into kernel, up to rck\_send\_notification(): 688 cycles
734 % %     * Sender: Time taken for rck\_send\_notification(): 927 cycles
735 % %     * Sender: Upon receipt of message from peer: 8371 cycles
736
737 % %    * As you can see, latency goes up the further the cores are away.
738
739 \section{Microbenchmark: Notification via MPB}\label{sec:mpb_bench}
740
741 We implemented a ping-pong notification experiment to evaluate the
742 cost for OS-level notification delivery via message passing buffers
743 (MPBs). MPB notifications are used in Barrelfish to notify a
744 user-space program on another core of message payload arrival on a
745 CC-UMP channel and are thus performance critical.
746
747 The experiment entails two peer cores sending notifications back and
748 forth. Based on their roles, we call these two cores \emph{initiator}
749 and \emph{collaborator}, respectively. The experiment is driven by a
750 user-space program on the initiator. After setup, one iteration of the
751 experiment is carried out in several steps. The experiment as depicted
752 by Figure~\ref{fig:mpbbench} is symmetric, thus we only describe the
753 steps carried out and observed by the initiator:
754
755 \begin{enumerate}
756 \item The initiator's monitor calls a special system call to send a
757   message directly to the collaborator and control is transfered to the
758   initiator's CPU driver.
759
760 \item The initiator's CPU driver writes the message into the collaborator's
761   MPB and sets the corresponding configuration registers of the collaborator
762   to raise its hardware INTR line.
763
764 \item The collaborator receives the message and replies, by carrying out
765   steps 4, 1 and 2 in that order \note{AB: unclear}.
766
767 \item The initiator's CPU driver traps upon receiving the interrupt,
768   determines the cause for the trap, reads the message from its MPB
769   and transfers control back to its monitor, which records the time
770   taken for all 4 steps.
771 \end{enumerate}
772
773 \begin{figure}
774   \centering
775   \includegraphics[width=6cm]{figures/exp1}
776   \caption{MPB ping-pong experiment setup}
777   \label{fig:mpbbench}
778 \end{figure}
779
780 % \note{AB: Need to describe clock speed config somehwere}
781
782 We carried out this benchmark between core 0 and all other cores
783 inside the system, measuring the round-trip latency for an MPB
784 message containing one cacheline, and halved the result to extrapolate
785 the one-way latency. Figure~\ref{fig:mpbresults1} shows the result, as
786 well as a break-down into interesting steps of the experiment.
787
788 \begin{figure}
789   \centering
790   \includegraphics[width=\textwidth]{plots/mpbbench/mpbbench_oneway.pdf}
791   \caption{MPB one-way messaging latency from core 0
792     (\emph{Overall}). \emph{Send} shows cumulative latency in steps 1
793     and 2. \emph{Receive} shows latency of step 4.}
794   \label{fig:mpbresults1}
795 \end{figure}
796
797 % Absolute numbers for IPI benchmark with optimization \texttt{-O3}, no
798 % interrupts, array: \note{Please clarify what this benchmark is what
799 %   ``array'' means.  Also, assume these are cycles as well?}
800
801 % \begin{center}
802 % \begin{tabular}{ p{0.2\textwidth}|p{0.3\textwidth}}
803 % op & cycles \\
804 % \hline \\
805 % send: & 800 (includes user-space): \\
806 % receive: & 2596 (includes user-space): \\
807 % round-trip with both monitors: &  7026 \\
808 % extrapolated one-way latency for short message: & 3513\\
809 % \end{tabular}
810 % \end{center}
811
812 \section{Microbenchmark: Inter-processor interrupt (IPIs) latency}
813
814 We modify the message latency ping-pong experiment described in
815 Section~\ref{sec:mpb_bench} to approximate the cost for hardware-level
816 inter-processor interrupt delivery. IPIs are used in Barrelfish to
817 notify another core of message arrival and are thus performance
818 critical.
819
820 The core roles are kept and the numbers presented are still for two
821 cores on the same tile. After setup, one iteration of the experiment
822 is carried out in 5 steps, as depicted by Figure~\ref{fig:ipibench}:
823
824 \begin{enumerate}
825 \item The initiator's monitor calls a special system call to send a
826   message directly to the collaborator and control is transfered to the
827   initiator's CPU driver.
828
829 \item The initiator's CPU driver writes the message into the collaborator's
830   MPB and sets the corresponding configuration registers of the collaborator
831   to raise its hardware INTR line.
832
833 \item The collaborator's CPU driver traps upon receiving the interrupt,
834   determines the cause for the trap, reads the message from its MPB
835   and immediately replies with another message to the initiator, using
836   the mechanism of step 2, upon which the initiator's CPU driver
837   traps.
838
839 \item Upon determining the trap cause, the initiator's CPU driver
840   reads the message from its MPB.
841
842 \item The initiator's CPU driver transfers control back to its
843   monitor, which records the time taken for all 4 steps.
844 \end{enumerate}
845
846 % \note{AB: This is more than an IPI!}
847
848 \begin{figure}
849   \centering
850   \includegraphics[width=6cm]{figures/exp2}
851   \caption{IPI ping-pong experiment setup}
852   \label{fig:ipibench}
853 \end{figure}
854
855 In this version of the experiment, which ran over 100,000 iterations,
856 eliminating the first 10\% of values, the average time for an IPI
857 round-trip is 8746 cycles. Table~\ref{tab:ipiresults} presents a
858 break-down of the measured costs. The measured average latency for
859 step $i$ is denoted as $\lambda_i$. We did not collect measurements
860 for all steps individually and some measurements are only made for
861 steps in combination.
862
863 We can then approximate the latency $\lambda_{IPI}$ involved to
864 deliver the IPI, including the time to execute the trap, by
865 $\lambda_{IPI} = \frac{\lambda_3 - (\lambda_2 + \lambda_4)}{2}$, the
866 total time spent inside the peer kernel, minus the time to send and
867 receive an IPI inside the local kernel, divided by two to yield the
868 time needed for only one trap (we are in a ping-pong loop).
869
870 Note that this is an optimistic approximation. As the local side
871 includes user-code to drive the benchmark, the measured latencies
872 inside the local kernel might be too large, due to missing cache lines
873 caused by executing user code. As this cost does not occur on the peer
874 kernel, where only kernel code is executed, the real cost for an IPI
875 might be higher. Furthermore, we only measured the cost for two
876 kernels on the same tile. The cost to deliver an IPI between cores of
877 far away tiles might be slightly higher.
878
879 \begin{table}
880   \centering
881   \begin{tabular}{p{0.2\textwidth}|p{0.2\textwidth}}
882     op & cycles \\
883     \hline \\
884     $\sum_{i=1..5}{\lambda_i}$ & 8746 \\
885     $\lambda_1 + \lambda_2$ & 1135 \\
886     $\lambda_4 + \lambda_5$ & 3864 \\
887     $\lambda_2$ & 684 \\
888     $\lambda_3$ & 3662 \\
889     $\lambda_4$ & 1754 \\
890     $\lambda_{IPI}$ & \textbf{612} \\
891   \end{tabular}
892   \caption{Measured and extrapolated IPI benchmark latencies}
893   \label{tab:ipiresults}
894 \end{table}
895
896 We consider a latency of at least 612 cycles to deliver an IPI very
897 high for it to be useful as a signaling primitive for the majority of
898 message sends in a message-passing system like Barrelfish.
899
900 \section{Application-level benchmarks}
901
902 The only other software environment presently available on SCC uses a
903 separate instance of the Linux kernel on each core. Above this runs
904 RCCE~\cite{intel:rcce}, a library for light-weight, efficient
905 communication that has been co-designed with SCC as a research vehicle
906 for message-passing API design on non-cache-coherent many-core chips,
907 and as such is highly optimized for this platform. RCCE runs in
908 user-mode with raw access to the MPBs, providing basic point-to-point
909 message passing functionality as well as a set of higher-level
910 primitives, such as barriers and a reduce operation, akin to those
911 found in MPI~\cite{mpi}.
912
913 We implemented a substrate supporting the RCCE message-passing
914 interface using Barrelfish stubs and interconnect drivers for
915 messaging, and thus can securely support multiple applications. We
916 evaluated the NASA benchmarks shipped with RCCE to compare the
917 performance achieved on Barrelfish to a system running 48 instances of
918 Linux, as used at Intel.
919
920 Figures \ref{fig:appresults_total} and \ref{fig:appresults_speedup}
921 show the result of this comparison. We can see that at the application
922 level, when a single application is run, Barrelfish does show only
923 slightly lower performance than 48 Linux instances. We attribute this
924 to the early version of our port. There is no reason why Barrelfish
925 should not have identical performance to 48 instances of Linux when
926 only a single application is run. We furthermore expect Barrelfish to
927 have better performance than the Linux setup when multiple
928 applications need to be scheduled on the SCC.
929
930 \begin{figure}
931   \centering
932   \includegraphics[width=.5\textwidth]{plots/rcce_bench/rcce_lu.pdf}%
933   \includegraphics[width=.5\textwidth]{plots/rcce_bench/rcce_bt.pdf}
934   \caption{RCCE benchmark absolute performance comparison}
935   \label{fig:appresults_total}
936 \end{figure}
937
938 \begin{figure}
939   \centering
940   \includegraphics[width=.5\textwidth]{plots/rcce_bench/rcce_lu_speedup.pdf}%
941   \includegraphics[width=.5\textwidth]{plots/rcce_bench/rcce_bt_speedup.pdf}
942   \caption{RCCE benchmark speedup comparison}
943   \label{fig:appresults_speedup}
944 \end{figure}
945
946 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
947 \chapter{Reflections on SCC as a platform}\label{chap:refl}
948
949 This chapter contains a set of reflections on the challenges of
950 implementing Barrelfish on SCC hardware.  It should be regarded as a
951 snapshot of our current thinking, rather than a definite set of
952 conclusions.  Indeed, as our understanding of how to effectively
953 exploit SCC as a platform evolves, we expect some of these views to
954 change.  We would warmly welcome any feedback or suggestions with
955 regard to this points.  
956
957 \section{Build environment}
958
959 SCC is a straightforward platform for us to build Barrelfish for -- we
960 already cross-compile for 32- and 64-bit Intel Architecture machines,
961 and the P54C is fully supported by gcc. 
962
963 Two features of the SCC development environment could be improved (or
964 were during the porting process): 
965
966 \begin{itemize}
967 \item The tools provided for board setup, initialization, console,
968   etc. were all GUI-based, making it impossible to script commonly
969   used processes.  All the boot tools used for Barrelfish at ETHZ and
970   MSR are command-line based, and fully automated (for example, our
971   regression tools start by powering on the machine and turn the
972   hardware off when done) and we use build-and-boot scripts
973   extensively.  The bringup process would have been considerably
974   faster with CLI tools for board control.
975
976   Many of these tools exist (partly as a result of our feedback), but
977   it would be helpful if the command-line interface was regarded as a
978   first-class requirement. 
979
980 \item A proper console driver (a low-level, bidirectional character
981   channel between the HCPC would have been very useful.  Our other
982   platforms (even Beehive) assume a low-level UART or analogous
983   hardware.  Our initial solution involved emulating a VGA character
984   frame buffer in shared memory, and reading this out from the host
985   PC, but this is highly unsatisfactory, and a better solution is a
986   synchronized ring buffer of characters in DDR3 together with a
987   logging daemon on the host which DMAs this regularly to the host,
988   and routes this to a Unix socket, for example.  Once again, GUIs are
989   of limited use here (though we appreciate their value in demos).
990
991 \end{itemize}
992
993 \section{Debugging}~\label{debugging}
994
995 The SCC platform has no debugging facility. Instead, memory regions
996 for per-core kernel log buffers were reserved on every core and later
997 dumped into files using external memory reader tools provided.  This
998 provided for convenient debugging, especially as we already use such a
999 technique for fine-grained tracing on x86-64 hardware.  We found that
1000 log buffers could always simply be made big enough to carry the whole
1001 record needed for one debugging or performance measuring session.
1002
1003 However, debugging timing-related issues, like races, was hard
1004 using this scheme, as there is no global clock inside SCC and so
1005 messages could not be reliably timestamped, making it unclear which
1006 messages are emitted at what times, when debugging processes that
1007 involve interactions between cores.  
1008
1009 A preliminary workaround for this would be to derive clock skew
1010 information online and log this when cores start, post-processing this
1011 information by extending our existing trace analysis tools.   Adapting
1012 our tracing framework to use Lamport clocks would be a more elegant
1013 solution. 
1014
1015 In the longer term, part of our research agenda is to deal with the 
1016 general clock problem in arbitrary machines, and so in this respect
1017 SCC is a useful case for us, the lack of synchronized clocks is
1018 actually a useful feature of the platform.  
1019
1020 \section{Lack of cache coherence}
1021
1022 We experienced no significant problems with Barrelfish due to the lack
1023 of coherent caches on the SCC.  This was not a huge surprise for us,
1024 but it was a nice confirmation of our expectations, and a validation
1025 of the OS design. 
1026
1027 As with the lack of clock synchronization, we regard the lack of
1028 coherent caches as a useful feature from a research perspective.
1029 Indeed, we would like to be able to (perhaps selectively) turn off
1030 cache coherence in more mainstream Intel processors. 
1031
1032 Much more useful to us would be the ability to have more than one
1033 memory write per core in flight (in particular, a simple write buffer
1034 would dramatically increase performance). 
1035
1036 \section{The L2 caches}
1037
1038 The caches (both L1 and L2) do not allocate a cache line on a write miss,
1039 treating it as an uncached write to memory. Furthermore, the M-unit allows the
1040 core to have only one outstanding write transaction; when such a write miss
1041 occurs, any subsequent memory or L2 cache access causes the core to stall
1042 until the write to memory completes (typically around 100 cycles on the SCC).
1043 Combined with the lack of a store buffer, this policy causes severe performance
1044 degradation for word-sized writes to data not already present in the cache.
1045 When storing to a fresh stack frame, or saving registers in a context switch
1046 path, each individual write instruction will stall the processor on memory
1047 access.
1048
1049 For example, in Barrelfish kernel code, we observed that simple
1050 function calls in hot paths of the system regularly have an order of
1051 magnitude greater overhead (in cycles) on SCC than function calls on
1052 newer x86 processors. Our tentative explanation is that caller-saved
1053 registers will be pushed onto the stack upon a function call and then
1054 restored upon return from the function. Both cases miss in the cache,
1055 but the call incurs particularly high overhead, as each individual
1056 write goes to memory, and the cache lines are only allocated when
1057 reading them on return. We do not yet have an explanation of why this
1058 is occuring every time after entering the kernel -- the logical
1059 behaviour for it would be to only occur once when the cache is
1060 cold. We have also observed substantially increased costs for
1061 exception and trap handling, which may also be caused by the high cost
1062 of saving register state to memory not present in the cache.
1063
1064 It is possible that an OS workload is a particularly bad case for this
1065 cache design -- systems software is well-known for exhibiting usage
1066 patterns very different to parallel HPC applications.
1067 More work is required to both confirm this as the cause, and explore possible
1068 solutions. Ideally this could be fixed in hardware, through changes to the
1069 cache architecture, the addition of a store buffer in the M unit, or simply
1070 allowing the write-combining buffer to be used for non-message-buffer memory,
1071 which would mitigate the problem by allowing full cache-line writes to memory.
1072 A possible software fix would involve reading from each cache line before it
1073 was written, to ensure its presence in the cache; in the case of context save
1074 code this could be done explicitly, but for stack access would probably
1075 require compiler modifications.
1076
1077 \section{Message-passing memory}
1078
1079 The ability to bypass the L2 cache for areas of address space
1080 designated messaging buffers, combined with an efficient L1
1081 invalidation of all such lines, is one of the most interesting
1082 features of SCC. 
1083
1084 As with other message-passing features of the SCC, this functionality
1085 may have been designed with a single-application system in mind.  When
1086 using MB memory for the operating system, as in Barrelfish, we
1087 typically have a number of communication channels in use at any one
1088 time. 
1089
1090 For this reason, although the CL1INVMB instruction is extremely cheap to
1091 execute, its effects may be somewhat heavyweight, since it invalidates
1092 all messaging data, some of which we may wish to have remain in the L1
1093 cache. 
1094
1095 It would be useful for us to have more fine-grained control over the
1096 L1 cache.  An instruction which would
1097 invalidate a region around a given address would be ideal for us.  
1098 The size of this region would typically be a cache line, but it would
1099 be fine if this was implementation-defined (as long as we could find
1100 out at run time).
1101
1102 In our message-passing implementations, we generally know precisely
1103 which addresses we wish to invalidate.  Consequently, we would find
1104 such fine-grained cache control very useful. 
1105
1106 Better still would be to extend such functionality to the L2.
1107 Receiving data in an MPB generally involves an L1 miss (ideally to
1108 the on-tile MPB, but see below why this is problematic), followed by
1109 a miss to main memory caused by copying the data somewhere where it
1110 can be cached in L2, followed by a second L2 miss when the data needs
1111 to be subsequently read. 
1112
1113 This penalty can be mitigated somewhat by performing a read of the
1114 destination location (and so populating the L2) before writing the
1115 received data there.  
1116
1117 This latter miss penalty itself is generally doubled, due to the
1118 non-write-allocate property of the L2: there's the immediate stall
1119 while the write completes to DDR3, followed by an L2 miss later when
1120 the core tries to use it.  This is ironic: the cache
1121 architecture seems to prohibit any efficient zero-copy I/O
1122 implementation, since if it's from MPB, it will be flushed any time
1123 further I/O occurs. 
1124
1125 Our position overall is that explicit cache management is good, and
1126 Barrelfish (and, we believe, other OS code) would benefit from future
1127 SCC implementations providing much more fine-grained control over it. 
1128
1129 \section{Lookup tables}
1130
1131 From the perspective of system software design, the SCC Lookup tables
1132 for physical memory are an interesting feature of the
1133 design.  In particular, being able to address any other core's
1134 configuration registers (including interrupt and reset pins), and that
1135 core's lookup table as well, is a powerful feature. 
1136
1137 At present, we do not exploit this functionality fully in Barrelfish,
1138 other than for booting secondary cores and sending inter-processor
1139 interrupts, plus the use of the TAS bit for interlocking access to the
1140 on-tile MPB.   More novel uses of the LUTs are an interesting area of
1141 future research for us. 
1142
1143 An interesting possibility, not explored by us at this stage, is to
1144 use the LUTs to completely ``sequester'' cores: by removing a core's
1145 access to its own LUT entries, its ability to access any system
1146 resources not its own can be tightly restricted.  This would allow us
1147 to provide stronger fault-containment properties than are possible in
1148 a shared-memory system, for example, which means that the
1149 message-passing structure of Barrelfish combined with suitable
1150 distributed algorithms at the intra-OS routing layer (which is a focus
1151 on ongoing work at ETH) may result in an OS tolerant to partial
1152 crash-failures or even Byzantine faults. 
1153
1154 Another direction is to explore using the LUT for context-switching by
1155 integrating it much more into the OS, rather than using the static
1156 mapping we have now.  We currently have no performance data for how
1157 quickly updates to the LUT take, however, which will be a factor in
1158 how useful such operations are in practice.
1159
1160 \section{Lock (TAS) bits}
1161
1162 Not having TAS bits on the SCC would have caused serious problems
1163 for us.  However, we did not encounter any need for more than one
1164 TAS bit per core.  Since almost everything in Barrelfish is performed
1165 with a messaging model, we simply use the TAS bit to synchronize
1166 access to the receiving core's messaging and IPI state.  One lock is
1167 enough.  
1168
1169 Our code would be simplified, however, if there was an operation to
1170 atomically assert IRQ on a remote core only if it has not already been
1171 asserted.
1172
1173 \section{The on-tile message passing buffer}
1174
1175 We experienced two significant challenges when using the on-tile
1176 message passing buffers on SCC.  These challenges are related, but
1177 different. 
1178
1179 \subsection{Size}
1180
1181 We are not the first to suggest that the on-tile MPBs are small. Small
1182 buffers mean that message queues have to be short.  If messages cannot
1183 be lost (a typical design assumption for message-passing applications,
1184 and at present also the case for Barrelfish), this means head-of-line
1185 blocking.  The smaller the buffer, the  shorter the queues, which
1186 means tighter coupling between communicating processes, making
1187 blocking on sends more likely. 
1188
1189 Barrelfish uses message-passing throughout for communication, and
1190 consequently requires a large number of independent message channels
1191 to share the MPBs.   This leads to the question of how to allocate
1192 space in the MPBs to message channels.  Assuming (for simplicity at
1193 this stage) that each channel is allocated resources on the tile where
1194 its destination core resides, the options are:
1195
1196 \begin{enumerate}
1197 \item Allocate a fixed portion of the on-tile MPB to each channel for
1198   payload.  The minimum allocation is realistically a cache line (32
1199   bytes), allowing a maximum of 256 incoming channel end-points per
1200   core in the 8192 bytes available.   This is quite small (think
1201   sockets), and even so allows only a single cacheline of buffering.
1202   Giving each channel a buffer of 8 cache lines would only allow us 32
1203   message channels per core, which is impractical. 
1204 \item Allocate a fixed portion of the on-tile MPB for channel
1205   metadata, and pass payloads in DDR3 RAM.   Without inter-core
1206   synchronization, this still requires a cache line per channel to
1207   avoid corruption due to concurrent writes, limiting the number of
1208   channels again to 256. 
1209 \item Allocate channel metadata in the on-tile MPB in units smaller
1210   than a cache line, and use the TAS registers to mediate access.
1211   With 16-bit pointers in memory, this allows 2048 channels per core,
1212   at the cost of TAS-implemented spinlocks to prevent corruption.
1213   This channel limit may be enough for Barrelfish, as we might then be
1214   able to use the MPB locations as a cache for active channels and
1215   ``swap'' idle channels to memory (though we have no idea if the
1216   workloads would make this feasible or not). 
1217 \item Multiplex all Barrelfish channels onto a single channel per pair
1218   of cores, requiring only 47 end-points in the on-tile MPB but kernel
1219   code to demultiplex incoming messages.  This allows 170 bytes of
1220   buffer per core pair, still small, but possibly useful for
1221   Barrelfish (which messages are small).  The penalty here is a kernel
1222   crossing, however (and see below for more on multiplexing). 
1223 \item Do away entirely with channels at this level, and since have
1224   each core take out a spinlock on a destination core (via TAS),
1225   followed by dynamic allocation in the whole 8k block.  
1226 \end{enumerate}
1227
1228 \subsection{Multiplexing}\label{sec:mpbmux}
1229
1230 The single most serious limitation of SCC as a platform for a
1231 message-passing OS like Barrelfish is the inability to securely
1232 multiplex the on-tile MPBs without a kernel-mode transition on the
1233 message path.    An operating system on the SCC must mediate access to
1234 the MPBs to ensure safe sharing of the buffers between applications. 
1235 This issue does not arise if the SCC is only running a single MPI
1236 application. 
1237
1238 This is ironic, since the very high performance of loads from and
1239 stores to the on-tile MPB is completely swamped by the cost of kernel
1240 crossing to validate the access.  We have, to date, been unable to
1241 come up with a good workaround for this. 
1242
1243 This strongly suggests that the intended use-case for the MPBs was
1244 single-application scientific computing, or perhaps the SCC chip as a
1245 dedicated, single-user ``accelerator'' (like a GPU), rather than a
1246 main processor in its own right.  
1247
1248 Let's look at this issue in more detail. Like most resources in a
1249 computer, the MPBs can be multiplexed in space, and in time. 
1250
1251 \subsubsection{The MPBs can't be efficiently space-multiplexed between
1252   applications} 
1253
1254 Space-multiplexing the MPBs requires a protection mechanism to divide
1255 the buffer between applications or other resource principals.  For
1256 main memory, this is performed by each core's MMU (on the SCC, the
1257 LUTs can do this as well).  The OS can allocate memory
1258 between different virtual address spaces in advance, but protection is
1259 enforced in hardware on every load or store (by the TLBs).  
1260
1261 This doesn't work with the MPBs, since the MMU can only guarantee
1262 protection at page granularity, and each core's MPB is only two
1263 pages.  Two applications per core is better than one, but not by
1264 much. 
1265
1266 The only way to enforce protection on MPB memory at a finer
1267 granularity is to delegate to the kernel the ability to read/write MPB
1268 memory, and pay the cost of a system call on every load and store. 
1269
1270 As an additional cost, since multiple cores can be expected to be
1271 accessing each tile's MPB (Barrelfish makes extensive use of ``message
1272 channels'' between application dispatchers on different cores), write
1273 access to each core's memory must be done under a lock (hence the use
1274 of the TAS bit for each core to protect the MPB). 
1275
1276 \subsubsection{The MPBs can't be efficiently time-multiplexed between
1277   applications}
1278
1279 Time-multiplexing the MPBs require copying each application's state
1280 into or out of the MPBs on a context switch, or performing this
1281 lazily.   This is potentially 8kb of message data, a substantial
1282 context-switch overhead (see the L2 cache discussion above). 
1283
1284 It's actually worse than that.  Unlike memory which is under the
1285 exclusive use of an application, memory used for communication between
1286 applications on different cores is shared between a pair of
1287 principals.  Time-multiplexing on-tile MPB memory entails highly
1288 complex co-scheduling of communicating principals on different cores,
1289 which severely constrains the system-wide schedule and requires
1290 considerable communication overhead in itself. 
1291
1292 \vspace{12pt}
1293
1294 In summary:
1295 \begin{itemize}
1296 \item Lack of fine-grained protection prevents efficient space-sharing
1297   of on-tile MPB without a kernel mediating all accesses. 
1298 \item The fact that the buffers are inherently shared between cores
1299   (because they are used for communication) prevents efficient
1300   time-sharing without a kernel mediating all accesses. 
1301 \item The cost of kernel entry and exit dwarfs any performance gain
1302   from the fast on-tile memory. 
1303 \end{itemize}
1304
1305 \section{Dynamic Voltage and Frequency Scaling}
1306
1307 The flexibility of the dynamic voltage and frequency scaling features
1308 of the SCC look particular interesting.  Unfortunately, to date we
1309 have not explored how to use them in Barrelfish. 
1310
1311 \section{System Interface}
1312
1313 We are only beginning to exploit the System Interface as anything 
1314 more than a development / boot feature.  A new Barrelfish interconnect
1315 driver which spans the PCI Express bus and allows seamless communication
1316 between Barrelfish dispatchers on SCC cores and host PC cores is in
1317 development. 
1318
1319 So far, we think the design of the software-visible aspects of the
1320 System Interface is nearly ideal from an OS design perspective.
1321 In particular, exposing flits to system software on the host machine
1322 allows us great  flexibility in how to communicate across the PCI
1323 Express bus. 
1324
1325 In general, as OS designers we favor exposing more hardware mechanism (and
1326 thereby increasing policy freedom) as much as possible, unless this
1327 entails removing functionality from the fast data path which is
1328 critical to performance (as would be the case with virtual address
1329 translation, for example). 
1330
1331 \section{Interrupt latency and notification}
1332
1333 A second reason for the relatively leisurely performance of Barrelfish
1334 on SCC is the cost of kernel crossings, coupled with the need to
1335 perform them frequently for messaging (see Section~\ref{sec:mpbmux}).
1336 This is the case both for system calls and interrupts, since asserting
1337 IRQ is the only way to send notifications to cores (rather than
1338 waiting for polling to complete). 
1339
1340 Part, but not all, of the overhead is due to L2 cache performance and
1341 lack of write-allocation.  
1342
1343 As OS designers, we would really appreciate a fast way to transition
1344 to kernel mode, and hardware which allows us to something useful and
1345 fast when we get there (such as scratch registers, or alternative
1346 register banks).  This is an area where the ARM architecture really
1347 shines. 
1348
1349 In addition, our experience with Barrelfish so far suggests that some
1350 kind of inter-core notification mechanism is an important complement
1351 to polled message-passing support.  The fact that we can access
1352 interrupt pins on cores remotely on the SCC is very nice in this
1353 regard, but even better would be some kind of fast user-space control
1354 transfer.  One option is to introduce address space identifiers (these
1355 should be orthogonal to virtualization in any case), and cause a
1356 lightweight same-address-space jump if and only if that address space
1357 is running. 
1358
1359 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1360 \chapter{Historical features}\label{chap:historical}
1361
1362 This chapter described features once present in older versions of
1363 Barrelfish that have been deprecated or superseded by newer
1364 functionality.
1365
1366 \section{Console driver}
1367
1368 Up to \verb+release2012-03-02+, there is no support for serial or VGA
1369 console hardware on the SCC, so the CPU driver contains no kernel-mode
1370 support for either and the Barrelfish user-level UART and VGA drivers
1371 are not supported.
1372
1373 Instead, console output is written into a core-local log buffer
1374 starting at address \texttt{0xb8000} in private RAM, which can be read
1375 by the \texttt{sccDump} tool on the host. The buffer size is
1376 configurable at compile time and defaults to 16,000 bytes.
1377
1378 This technique evolved from the x86 VGA driver and is why the buffer
1379 originates at address \texttt{0xb8000}, the x86 text-mode buffer. We
1380 have removed VGA control character emission and are instead writing C
1381 strings as given into the buffer. This turned out to be the simplest
1382 way to achieve readable console output without having to write
1383 additional tools on the host to receive console characters emitted by
1384 kernels running on the SCC.
1385
1386 We have developed a shell script to run on the host to periodically
1387 re-read a specified core's log buffer at a frequency of roughly 10
1388 times a second and output it to the host's console, so the log buffer
1389 can be displayed analogous to a monitor displaying the contents of
1390 video memory. As it evolved from the x86 VGA driver, our console
1391 driver will rearrange the contents of the log buffer when its capacity
1392 exceeds by assuming an 80x25 character matrix layout and moving all
1393 rows ``up'' by one matrix row position, eliminating the top row,
1394 freeing up another row of characters for more console output, just
1395 like a VGA driver would produce a line feed on an x86 VGA
1396 terminal. When the terminal on the host has equal dimensions, this
1397 technique provides an identical effect on the host terminal.
1398
1399 A drawback with this technique despite suboptimal performance and
1400 logging capabilities is the inability to map console output across
1401 cores to a global timeline. There is no global clock inside the SCC,
1402 so timestamps on log messages do not help. We elaborate more on this
1403 in Section~\ref{debugging}.
1404
1405 Obviously, this technique is a kludge and does not represent what
1406 could be done if proper console support were provided via the SCC
1407 system interface by additional software written on the host. We assume
1408 that standard UART support via the system interface would provide
1409 sufficient performance while moving all buffering capabilites into the
1410 host and providing a single concentrator for console output by all
1411 cores of the SCC simultaneously, eliminating the global timeline
1412 problem.
1413
1414 \section{MPB emulator}
1415
1416 As part of development, an MPB emulator for x86-32 was created. It was
1417 available up to version \verb+release2012-03-02+. The emulator is
1418 implemented as a device driver for the SCC CPU driver and replaces the
1419 original SCC device driver, exporting an identical interface.
1420
1421 This emulator was used for functional testing and debugging of the SCC
1422 user-space interconnect driver and message passing stubs, as well as
1423 the ported RCCE library and user-space applications, without the
1424 need for access to a real SCC.
1425
1426 As the emulator allowed us to compile and run the SCC CPU driver
1427 largely unmodified on a standard ia32 core, it was also used for
1428 initial testing of the SCC boot process, before gaining access to real
1429 SCC hardware for the first time.
1430
1431 The emulator uses a region of unmapped RAM on an x86 for the
1432 MPBs and sends inter-core interrupts using the local APIC IPI
1433 mechanism. Configuration registers are unsupported. Core IDs are
1434 reported from the local APIC core ID register.
1435
1436 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1437 \bibliographystyle{abbrv} 
1438 \bibliography{defs,barrelfish}
1439
1440 \end{document}
1441
1442 \end{document}