Ignore:
Timestamp:
Jun 13, 2012, 5:29:11 PM (7 years ago)
Author:
boender
Message:
  • more progress
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/ASM/CPP2012-policy/problem.tex

    r2054 r2064  
    6767
    6868The canonical solution, as shown in~\cite{Szymanski1978} or more recently
    69 in~\cite{Dickson2008} for the x86 instruction set, is to use a fixpoint
     69in~\cite{Dickson2008} for the x86 instruction set, is to use a fixed point
    7070algorithm that starts out with the shortest possible encoding (all jumps
    7171encoded as short jumps, which is very probably not a correct solution) and then
     
    7979can be used; above this value the jump must be encoded as a long jump.
    8080
    81 Here, termination of the smallest fixpoint algorithm is easy to prove. All
     81Here, termination of the smallest fixed point algorithm is easy to prove. All
    8282jumps start out encoded as short jumps, which means that the distance between
    8383any jump and its target is as short as possible. If we therefore need to encode
     
    8686reasoning holds throughout the subsequent iterations of the algorithms: short
    8787jumps can change into long jumps, but not vice versa. Hence, the algorithm
    88 either terminates when a fixpoint is reached or when all short jumps have been
    89 changed into long jumps.
     88either terminates when a fixed point is reached or when all short jumps have
     89been changed into long jumps.
    9090
    9191Also, we can be certain that we have reached an optimal solution: a short jump
     
    147147as medium jumps. Depending on the relative sizes of long and medium jumps, this
    148148solution might actually be smaller than the one reached by the smallest
    149 fixpoint algorithm.
     149fixed point algorithm.
    150150
    151151\begin{figure}[h]
Note: See TracChangeset for help on using the changeset viewer.