directly need are obvious. However, usually when making changes to the main LLVM
code, just changing enough for Recore is not engough for LLVM. Since the LLVM
code must work on any program, not just MontiumC programs, extra changes are
-required. This is also an issue of building up credit within the LLVM community:
-The more you contribute to LLVM, the more influence you have when things need
-changing. Lastly, this is also a matter of efficiency: If I have been working
+required (see also parapgrah \ref{StayingGeneric}. This is also an issue of
+building up credit within the LLVM community: The more you contribute to LLVM,
+the more influence you have when things need changing.
+
+Lastly, this is also a matter of efficiency: If I have been working
with a particular piece of code intensively, it is more efficient for me to fix
a bug in that code than most others, even though the particular bug does not
interfere with the MontiumC frontend. In the end, I think I managed to find a
writing code, if I can think of enough things to say here.
\subsection{Working together}
-This section says something about working with colleagues in various ways.
+Since the compiler plays a fairly central role in the development process at
+Recore, I have been cooperating with a number of different people, in different
+areas. On one end, the compiler is directly used by the DSP engineers, so a lot
+of the requirements and wishes for the compiler come from them. Also, they are
+often providing bug reports and other feedback, which ensures regular contact.
+
+On the other end, I have been in contact with the developer of the backend very
+intensively, since most changes made to either component needed changes in the
+other one as well. So compiler changes also require hardware support, so working
+with the hardware developers was not uncommon either. In practice, most of this
+communication went through the backend developer, except for the design
+discussion concerning the new Montium hardware design (also see section
+\ref{Pipelining} below).
+
+In addition, discussions regarding design issues at various levels often happen
+out in the open, which easily invites people with an opinion about something to
+chime in, without having to gather people around for every discussion that
+happens. This allows for very quick feedback on ideas from people in all areas
+in an efficient way.
\subsection{Staying generic}
\label{StayingGeneric}
-This section says something about the challenge of writing generic code:
-(changes to) transformations that are useful for both LLVM (ie on regular
-architectures) as well as for Recore (on the Montium).
+The toughest challenge by far was to fit the features and changes required by
+Recore into code that is maintained by the LLVM project. The main problem here
+is clash of goals: The LLVM project aims for code that performs well on their
+supported architectures, while Recore aims for code that performs well (or more
+often, can compile at all) on the Montium architecture.
+
+In general, these problems mainly occur because MontiumC and in particular
+MontiumIR poses a number of constraints that are not present in other
+architectures. This means that some transformations present in LLVM will violate
+these constraints (which would result in better code on most other
+architectures) resulting in miscompiled or uncompilable code.
+
+In some cases, these extra constraints can be formulated in a generic way, such
+that the LLVM code can handle architectures with or without the constraint.
+In a lot of cases, however, the constraint is so Montium specific that changing
+LLVM to support it is not feasible. In a few cases, this meant that the backend
+was changed to support more features of the LLVM IR. In other cases, a
+Recore-specific pass was added to solve these problems. In a few more cases, the
+problems are still unresolved, effectively resulting in additional constraints
+on the MontiumC language.
\subsection{Pipelined scheduling}
+\label{Pipelining}
I've also been involved for a bit with the instruction scheduling algorithm
required for the new (pipelined) hardware design. Even though this is completely
outside of the area of my assignment, the initial prototype of that scheduler
with thinking about the scheduler and hardware design.
I will not go into much detail about the new hardware and its scheduler here,
-but I will highlight the most important challenges and tradeoffs. I'll also
+but I will highlight the most important challenges and tradeoffs.
+
+In general, the most important tradeoff seems to be between flexibility and
+everything else (code size, performance, complexity). This flexibility is
+expressed in which instructions are possible, which connections are present, how
+big register files are, etc.
+
+An important reason to be flexible is for programmability. If the hardware is
+regular, making a compiler that produces optimal code gets a lot easier.
+On the other hand, the compiler also limits flexibility. If the hardware
+has flexibility that the compiler will never use, it's better to save
+area and complexity by making the hardware less flexible.
+
+When trying to improve runtime performance, the main focus is on
+optimizing loops, and inner loops (loops that contain no other loops) in
+particular. Since the inner loop is executed the most, it is the most
+efficient to optimize the inner loop. Also, the inner loop is also the
+piece of code that can most optimally use the parellel processing power
+of the Montium, because it can be software pipelined.
+
+This means that the compiler will emit code that performs operations
+that belong into different iterations of the original loop in the same
+cycle. Since data dependencies within a loop body usually severely limit
+the amount of operations that can be done in parallel, pipelining allows
+the second (and more) iteration to start well before the first iteration
+is done. This is done by dividing the loop body in a number of stages,
+that would normally be executed sequentially. These stages are then
+executed in parallel, but for different iterations (ie, run stage 2 of
+iteration i, while running stage 1 of iteration i+1).
+
+This approach allows a loop to be ran a lot faster than executing a
+single iteration at a time. However, since the instructions for the
+first and last few iterations (the prologue and epilogue) are distinctly
+different from the loop "kernel", the number of instructions needed for
+a pipelined loop can easily increase a lot.
+
+However, all pipelined loops share a very distinct structure (first
+stage 1, then stage 1+2, then stage 1+2+3, etc, then all stages at the
+same time, similar for the epilogue). Also, every instruction in the
+prologue and epilogue are a strict subset of the instructions in the
+kernel. By adding some hardware support for exactly this structure, the
+code size increase for the prologue and epilogue can be effectively
+reduced to a fixed number of instructions.
+
+Performance - inner loops
+Code compression.
+
+I'll also
spend a few words on the observed merits of hardware/software codesign.
+
+
projects / matthijs / projects / internship.git / blobdiff