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