\section{XOrder}
\label{Se:XOrder}
XOrder is an analysis that determines an improved layout for the
fields of a record type. It identifies these reorderings by analyzing the
results of XRef analysis. The experiments reported in \sectref{exp:xorder},
show that, without programmer intervention, XOrder can reduce the rate of
false conflicts for programs running on a transactional memory system.
\begin{definition}
\label{De:falseconflict}
A false conflict occurs when two distinct dynamic transactions access
separate bytes of memory, but, due to the conflict-detection scheme of
the transactional memory system, one of them is forced to stall or abort.
\end{definition}
Although false conflicts can occur in both STMs and HTMs, they are
especially prevelent in HTMs that detect conflicts using the coherence
mechanism. For clarity, in this section, we assume an HTM.

\begin{figure}
\begin{center}
\ifpdf
\includegraphics[width=35mm,height=25mm]{Images/FalseConflict.jpg}
\else
\includegraphics[width=35mm,height=25mm]{Images/FalseConflict.eps}
\fi
\end{center}
\caption{Possible layout in memory of the shared record {\tt s}
from \figref{Example}. Each row represents one cache line of memory.}
\label{Fi:FalseConflict}
\end{figure}

In our target HTM implementation, the granularity of precision is one cache
line. Therefore, during a dynamic transaction, the HTM's conflict-detection
mechanism
does not distinguish between memory reads and writes to the same cache line.
\figref{FalseConflict} depicts a possible layout in memory of the shared
{\tt ColoredShape} record \texttt{s} from the program in \figref{Example}. Assuming that
integers occupy four bytes of memory and that the cache-line size is sixteen
bytes, accesses to any of the fields \{\texttt{r, g, b, x1}\}
will be treated equally by the HTM's conflict-detection mechanism. Similarly,
accesses to any of \{\texttt{y1, x2, y2, x3}\} will not be distinguished and
accesses to any of \{\texttt{y3, x4, y4}\} will not be distinguished.
This memory alignment, combined with the HTM's
conflict-detection mechanism, will cause a false conflict
between the concurrent execution of transactions
({\tt n2},{\tt n3}) and ({\tt n1},{\tt n4}) from the program in
\figref{Example}. It is a false conflict because
the two transactions do not access any common fields of the shared
\texttt{ColoredShape} record \texttt{s}. To tackle this problem, we developed an
analysis algorithm, XOrder, that determines an optimized
layout ordering for record types. 

Record-layout reordering is a technique that analyzes which fields of
a particular record type might be accessed in a dynanic
transaction. The result of XRef is the set of fields of record types
accessed in a static transaction.  Thus, XRef computes a superset of
the fields actually accessed in a dynamic transaction. The idea behind
record-layout reordering is that if two fields, $f_1$ and $f_2$, are
accessed only in separate dynamic transactions, then the layout of the
record type in memory should be chosen to ensure that these fields
reside in separate cache lines. Because we are performing static
analysis, we do not know where in memory a record instance will be
dynamically created, and furthermore we do not know its alignment with
respect to cache lines.  Therefore, our goals are: (1) to separate
$f_1$ and $f_2$ with fields that are not accessed in a static
transaction, and (2) to ensure that the sum of the sizes of these
``padding'' fields is greater than or equal to the size of a cache
line. A beneficial byproduct of this ordering is that the number of cache
lines accessed by a dynamic transaction is potentially decreased.  This is
akin to the {\em cache-block working set} optimization described by Chilimbi
et al. in \cite{CDL99}.


XOrder uses the field annotations inferred by XRef to determine an optimized
ordering of a record type's fields. With respect to \cite{CDL99}, we do not
use dynamic profiling information to determine a field ordering. Instead, we
rely on the field accesses that occur in a static transaction.

Intuitively, the ordering determined by XOrder should be such that each static
transaction accesses a contiguous region of memory. When the fields accessed
by a static transaction do not overlap with the fields accessed by any other
static transaction, determining this ordering is trivial.
We create an undirected graph, where the nodes of the graph correspond to the
fields of the record type. There is an edge between two nodes (fields) if they
are accessed in the same static transaction. In \figref{Graph}, the {\tt x}
fields are all connected because they are accessed in the static transaction
({\tt n1},{\tt n4}) and the {\tt y} fields are all connected because they are
accessed in the static transaction ({\tt n2},{\tt n3}).
When ordering these fields, each connected component represents nodes that
should be laid out near each other. A (linearization of a) spanning tree for the
connected component gives a linear order for those fields.

In some cases, the accesses of two static transactions will share some subset
of a record type's fields. We refer to these static transactions as a
transactional group.
\begin{definition}
\label{De:TransactionalGroup}
A transactional group consists of 2 or more static transactions such that
there is a common field shared between at least two of the static transactions
in the group.
\end{definition}
In these situations,
%finding {\em any} spanning tree is not enough to
%determine the desired ordering. That is, finding a spanning tree for the
%transactional group and then linearizing the tree may result
%in an ordering that can still cause false conflicts.
%To combat this, we order the fields of each transactional group such that the
%fields common to multiple static transactions are placed near each other. This
%can reduce false conflicts when all the fields associated with a transactional
%group do not fit within one cache line. This is because fields that are unique
%to one static transaction will be as far away from the unique fields of other
%static transactions. For example, if a field common to two static transactions
%of a transactional group is a large array, placing this array between the
%fields not common to the static transactions of the transactional group could
%separate these fields by a cache line.\footnote{The model programming language
%used in this paper does not include arrays; however, our implementation is able to handle {\tt C}
%programs (including ones that use arrays).}
%
%Intuitively, the fields of a transactional group should be ordered such that
the fields of a transactional group are ordered such that
each static transaction of the group accesses contiguous regions of memory.
One solution to find such an ordering (if it exists) is to solve an instance
of the traveling-salesman problem (TSP). Create a graph where
the nodes of the graph represent the fields of the transactional group. For
each pair of nodes, add a weighted edge to the graph. The weight of the
edge is determined by the static transactions of the group. That is, if the
two fields represented by the nodes are accessed in the same static
transaction, then the weight is 1. Otherwise, we set the weight to be greater
than 1. By setting the weight to be greater than 1, a solution to the TSP
will not traverse that edge unless it is absolutely necessary. In our
experiments, we used the weight 10. For such graphs, an optimal solution to
the TSP will produce the desired ordering. The path can be used to create the
record layout. If it is possible for every static transaction of the group to
access contiguous memory, then this ordering will provide it. In cases where
no such ordering exists, the ordering produced by solving the generated
instance of the TSP will provide a good approximation.

Because we are targeting our analysis for a compiler infrastructure, solving
an NP-complete problem like the TSP every time the program is modified might
be too costly. Therefore, we use the well-known heuristic of using a
minimum-spanning-tree (MST) algorithm to approximate the TSP \cite{CLRS}.
Approximating the TSP solution using an MST is nice because it still takes the
graph's edge weights into account. For example, one could imagine 
using dynamic-profiling information to adjust the weights on the graph,
effectively biasing the solution to the TSP to prefer certain paths
(orderings) over others. This would allow XOrder to perform an optimization
akin to the {\em field-layout-affinity} method proposed by Chilimbi et al.
\cite{CDL99}. Because we use an MST to approximate a solution to the TSP, we no
longer need to distinguish between transactional groups and static
transactions (that are not members of a group). This is because we can use a
linearization of the MST to compute an ordering for both cases.

\begin{figure}
\begin{center}
\MediumScale\VCDraw{%
\begin{VCPicture}{(-4,-2)(4,2)}
\ShowFrame
\ShowGrid
%\ChgStateFillStatus{vlines}
\ChgStateLineStyle{dashed}
\State[x_1]{(-3.5,1)}{x1}
\State[x_2]{(-1.5,1)}{x2}
\State[x_3]{(-3.5,-1)}{x3}
\State[x_4]{(-1.5,-1)}{x4}

\ChgStateLineStyle{dotted}
%\ChgStateFillStatus{hlines}
\State[y_1]{(3.5,1)}{y1}
\State[y_2]{(1.5,1)}{y2}
\State[y_3]{(3.5,-1)}{y3}
\State[y_4]{(1.5,-1)}{y4}

\RstStateLineStyle
\State[r]{(0,1.5)}{r}
\State[g]{(0,0)}{g}
\State[b]{(0,-1.5)}{b}

\ChgEdgeArrowStyle{-}

\EdgeL{x1}{x2}{}
\EdgeL{x1}{x3}{}
\EdgeL{x1}{x4}{}
\EdgeL{x2}{x3}{}
\EdgeL{x2}{x4}{}
\EdgeL{x3}{x4}{}

\EdgeL{y1}{y2}{}
\EdgeL{y1}{y3}{}
\EdgeL{y1}{y4}{}
\EdgeL{y2}{y3}{}
\EdgeL{y2}{y4}{}
\EdgeL{y3}{y4}{}

\end{VCPicture}}

%\ifpdf
%\includegraphics[width=35mm,height=25mm]{Images/Graph.jpg}
%\else
%\includegraphics[width=40mm,height=30mm]{corr3.eps}
%\fi
\end{center}
\caption{The graph generated during XOrder analysis for the program in
\figref{Example}.}
\label{Fi:Graph}
\end{figure}

Once the layout of each static transaction and transactional group is
determined, we next use the record type's fields \emph{not} accessed in a static
transaction as padding between these orderings. If there are $n$ ordered sets,
then XOrder attempts to find $n-1$ sets of padding fields such that the size
of each set is at least the size of the cache line for the target
architecture. To do this, we sort the padding fields in decreasing order by
their size and then (attempt to) greedily fill the $n-1$ sets.
\figref{Reorder} displays the layout of  
\texttt{ColoredShape} after analyzing the program in \figref{Example} with
XOrder. Notice that the analysis suggested the insertion of an integer field
named {\tt pad1}. This is because for the example program 
(and target architecture with a cache-line size of 16 bytes),
there are not
enough fields to place between the two static transactions. Our analysis only
suggests the padding in a comment instead of directly emitting it because the
addition of extra fields can impact the performance of a program. For example,
if the program allocated a million {\tt ColoredShape} objects, then the
addition of the padding field would cause 4 MB of memory to be wasted.
Additionally, adding pad fields will affect the runtime behavior of the
program because it places extra pressure on the cache. Because of the padding
suggestions, we do not directly modify the analyzed program. Instead, we emit
the reorderings for each record type to the programmer. The programmer can
then decide whether to apply the reordering.
\input{CSquareReorder}

\subsection{Discussion}
\label{Se:XOrderDiscussion}
XOrder analysis is a whole program analysis. Field reordering can break
programs that make use of shared libraries that are compiled assuming a
certain field layout.  In addition to this, some programs write 
data to a persistent store. Reordering of fields can cause an
incompatibility with the data in the persistent store. However, if the
benefits from field reordering are large enough, we imagine the programming
effort required to make use of these fields is justifiable.

\subsection{XOrder Experiments}
\label{Se:exp:xorder}

\input{Benchmarks} We evaluated XOrder on three programs from the
SPLASH-2 benchmark suite \cite{woo:splash2:isca:1995}, modified to use
transactions in place of locks \cite{moore:logtm:hpca:2006}. The
SPLASH-2 programs are written in {\tt C}.\footnote{The {\tt C}
programming language is neither typesafe nor memory safe. Because of
this, both XRef and XOrder are unsound. The application of XRef and
XOrder analyses to a type and memory safe language would be sound.}
%We use the weighted pushdown system library WALi \cite{WALi}
%as our dataflow analysis solver.
%%%%% TODO: NAK rework this in?
%We extended CIL \cite{DBLP:conf/cc/NeculaMRW02} to extract a WPDS from the
%\texttt{C} code. 
%Our dataflow transformers are represented with BDDs, using
%the BuDDy \cite{buddy} BDD library.
%The analysis results returned from WALi
%are then fed into XOrder's record-layout engine.
%XOrder's record layout engine used the {\tt ocamlgraph} library
%\cite{ConchonFilliatreSignoles05} for all graph manipulations.
We modeled a 32-processor SPARC multiprocessor
running Solaris 9 with support for HTM using the Simics full-system
simulator \cite{magnusson:simics:ieeecomputer:2002} extended with a
detailed memory system timing model from the GEMS
\cite{martin:gems:can:2005,gems:website} toolkit.  Our simulated
system includes 32, 1 GHz SPARC processors each with 4 MB of private
cache.  The system includes HTM support based on LogTM
\cite{moore:logtm:hpca:2006}, which performs conflict detection at the
cache-line granularity.  For our experiments, we used a cache line
size of 64 bytes.

We compare the performance of the programs in their original form and
the programs modified to use the orderings suggested by XOrder. For
each of our benchmarks, we run both version of the program on our
simulated machine with a range of thread counts.  \tableref{Summaries}
displays the effect of the reordering on the overall runtime of the
benchmarks and on the frequency of transaction aborts, a major
contriubtor to the execution time.

Not surprisingly, our results vary for each benchmark. For Raytrace,
despite having little effect on the number of aborts, the reordering
provided by XOrder results in a dramatic improvement in performance (a
factor of 2.8 for 32 threads).  This result matches Moore et al.'s
observation that Raytrace suffers from false conflicts.  The
performance improvement is primarily due to the improved scalability
of the benchmark.  As shown in \figref{raytraceSpeedup}, eliminating
the false conflicts between transactions allows the reordered Raytrace
to continue to scale to 32 threads, while the original program
performance degrades after 16.

On Radiosity, XOrder at first appeared to provide an improvement. The number
of aborts steadily decreased up to 16 processors. However, However, the number
of aborts increased and performance worsened for 32 processors. We are
currently modifying the simulator to track additional processor state, e.g, we
are not able to separately measure true and false conflicts at this time. This
will help shed insight on the cause of the performance loss.

%performance was
%improve performance.seems to have little effect, improving
%performance for 16 threads, but degrading peformance for 32. We expect
%% FIXME
%that many workloads will not be improved by XOrder as they exhibit
%little to no false conflicts.  

For MP3D, on 16 processors, the layout XOrder suggested caused an increase in
the number of aborts which degraded performance for 16 threads. For 32
threads, despite a small increase in aborts, performance is unaffected.

Although our measured results show improvement in only one of our test cases,
we believe XOrder can still be a help to programmers.  XOrder found the
performance bug in Raytrace immediately. For MP3D, it was already tuned to
avoid false sharing.  Our future work includes analyzing more benchmarks and
further investigating the behavior of Radiosity. Hopefully, the investigations
can help us improve XOrder's field layout algorithm.
