Overall I find that this article has many errors in its presentations. Examples in Figure 3 and 5 seem to have mistakes in them (or older versions of the figure). So although I did not thoroughly check the proofs, I would not be surprised if there were errors in that as well. The overall idea and approach seems to be correct in reducing the latency and jitter. I find that this approach is just providing a restriction for SDF schedules such that output is produced every callback invocation and sufficient tokens are added as delays for correct schedule execution. I also don't see what they mean by timelineness in their title.

0/1 ILP formulation.

Optimal with respect to a profile run – uses access frequencies of variables measured from profile run.

Distributed stack: otherwise, programmers and compilers assign the whole stack to one kind of memory.

Disadvantages of caches: timing unpredictability, cost, power consumption.

Formulation for global variables

* Variables are treated atomically. This includes arrays. So an array will reside entirely in one memory unit.

* Allocation is compile-time and static – it is decided at compile-time where each global variable will sit, and it's not changed throughout the execution.

* Based on profile data – run the program a few times and collect frequencies of accesses to all variables. Thus, we will sort of minimize average time.

* Memory units have constant latencies. And looking at the objective function, it seems the latency is constant irrespective of sizes of variables! Incorporating sizes wouldn't be difficult.

* Only one memory access per cycle – modeling overlapping accesses requires max function, which is nonlinear.

If there are U memory units, and G global variables, have 0/1 variables I j(v i), which is 1 if variable v i is allocated in memory j. Add constraint saying that a variable can exist in exactly one memory unit. Add size constraint for each memory unit using sizes of variables.

Objective function is just total access time given the access frequencies of all variables.

With only two memory units (e.g. a cache and main memory), the formulation is exactly a 0-1 knapsack problem. With multiple units, it's like having multiple knapsacks. QUESTION: do people talk about multiple knapsack problem? Didn't see such thing on wikipedia.

QUESTION: what is more efficient method for solving knapsack problem – a specialized algorithm (e.g. dynamic programming), or ILP?

Extension to stack variables

Stack is distributed across all memory units. So different variables can be allocated to different memory units. Problem: function call overhead increases, as multiple stack pointers must be updated. Hence, alternative 1: all the variables of a function reside in one memory unit. Alternative 2: the original unrestricted case. Use hybrid approach: 1 for small functions, 2 for big functions.

Introduce additional variables for each of the function variables. For alternative 1, whole stack frame of a function is treated as one variable. From earlier formulation, only the size constraint gets complicated: instead of one global size constraint per memory unit, there is one size constraint for every path from the root to leaves in the call graph.

Because this is static allocation, it is context-insensitive: even if a function is called from multiple places, allocation of its variables is fixed.

Storage types: static, stack, heap, literals.

Access types: scalar, regular, irregular and input-dependent accesses. Regular means regular array access. Scalar and regular mean no pointers. Irregular uses pointers but is not input dependent.

Table 2 gives statistics of access and storage types for worst-case execution path of programs. QUESTION: why just worse-case path?

Conclusion: no heap accesses, but all access types for static and stack data.

Pointer analysis

Pointer analysis of GCC 4.1 is used to calculate all possible target addresses of every load/store instruction.

QUESTION: how effective is this target calculation? Does it usually come up with a small number of targets for a load/store instruction? The paper doesn't present results on this, but it will have impact on allocation, because constraint 8 says that all targets of a load/store must be either all present or all absent in the scratchpad.

WCET analysis

Uses Heptane to obtain WCET and corresponding path in a program. The path is represented by number of times each basic block is executed along the path.

For the analysis, you need:

What's exactly estimated contribution to WCET reduction for data v scratchpad-allocated on edge e_j?

Why subtract load store times from objective function?

All constraints except the one imposing size of scratchpad memory are binary. Can SAT techniques be used on such optimization problems?

Why allocation, de-allocation on edges and not in nodes? (in node means at the boundary of node, for example, at the start or end of a basic block.)

What are the fallouts of constraint 6? It says that scratchpad contents must match on all outgoing edges of a node.

Constraint 8 says that all the targets of a load/store instruction must be present or absent together in the scratchpad. What is the effectiveness of pointer analysis? Does it always come up with small number of targets for a load/store? Section 3.2.2 somehow relates this with architecture being static- or dynamic-scheduled. Didn't understand that.

Data placement

ILP formulation doesn't consider fragmentation. So, not all allocations will fit in the scratchpad.

Question about address assignment to data region – it starts with the data region having the highest impact in WCET reduction. Let's say that region is somewhere downstream in the flow graph. So it is allocated first and gets the address 0 in the scratchpad. If the second-highest data region does not overlap with the first and it precedes first. So do we put it at address 0 or elsewhere? It seems valid to put it at address 0 if it's going to be evicted before first data region starts.

Does data region end with a store? Yes it does.

engineer."

The implementation of the Giotto program, which requires no interaction with the control engineer is decoupled from the first task and can for the most part be automated by increasingly powerful compilers. Giotto can be compiled on different and even heterogeneous platforms. Basic functionality is the task (i.e. a periodically executed piece of code), and several concurrent tasks make up a mode. Tasks can be added or removed by switching from one mode to another. Tasks communicate with each other via drivers (code that converts and transports values between ports). Drivers are essentially bounded code that is assumed to execute instantaneously on the system. Giotto integrates scheduled computation (tasks) and synchronous communication (drivers). A Giotto program does not specify where, how and when tasks are scheduled. A Giotto program with tasks t1 and t2 can be compiled on platforms with a single CPU(by time sharing two tasks) as well as on platforms with two cpus(by parallelism). It can also be compiled on platforms with a preemptive priority scheduling (such as most real-time operating systems) as well as truly time-triggered platforms(such as the time-triggered architecture). The Giotto compiler just needs to ensure the the semantics of the program i.e functionality and timing - is preserved. So the compiler needs to solve a possibly distributed scheduling problem. The distributed scheduling problem can be rather difficult, so to make the job of the compiler easier a Giotto program can be annotated with compiler directives in the form of platform constraints i.e. you map a particular task to a particular cpu, assign a particular priority to a particular task or schedule a particular communication, or schedule a particular communication event between tasks in a particular slot.

problems for developing tight worst case execution time bounds. In

general, determining WCET requires managing all possible paths that a

program can execute as well as managing all the states that a program.

For example, if the state of a cache affects how long a memory

operation will take, then any WCET analysis that hopes to be tight

must manage the possible states of the cache. This is exacerbated by

the abundance of hardware components that have state that affects

their timing, as well as the interaction between these components and

the flow of control or data memory of a program. They contend that

the problem of managing all these possible states is one of the

largest problems in WCET analysis.

They then present two possible approaches to hierarchically managing

WCET analysis by partitioning hardware into components and then

composing those analyses. Each of these two approaches makes

different requirements of the hardware, and can only be used when that

requirement is met. The first, called "Delta-Composiotion" , can only

be applied when the effect of changing the state of one component on

the whole program cannot be larger than the effect to the timing of

that one component. The second, called "Max-Composiotion" , can only

be applied when the relative utilization of a hardware component over

a pair of states is the same as the relative utilization of a larger

system over those same states. They then assert that on any systems

where at least one of these requirements is met, WCET analysis is made

more feasible.

Couple things need more explanation. The protocol explained between the Execute Processor and the Access processor involves only small (16 byte) buffer. However, this is where they claim the performance gain comes from, and where the difference between this and a cache hierarchy. Basically,a cache will miss and this architecture supposedly gains by not missing and also prefetching. This comes from knowing which memory location to fetch, which this paper just refers to as a compiler output, but lack explanation. It was quite confusing to me how the Execute Processor relayed address information to the Access processor. I think more background reading is required from the related work section where it has some papers on compiler techniques, maybe we will get a better understanding.

The authors indicate that there is a paradox of incorporating time in high-level models. That is, accurate time information is only available at low-level abstractions and specifying time at high-level models is an approximate at best. They propse an approach similar to PBD where the specification pushes constraints to the implementation and the implementation can tell whether it is possible or not and if not, the specification is adjusted.

The two approaches are implemented with the two access pattern schemes with an application. This application is evaluated to show that the second approach of including the DMA memory access in the WCET analysis of the individual application tasks provides tighter estimation and enables more processing resources for teh application.

The timing tree is a simplified syntax tree designed to communicate the maximum time analyzer and the time editor. Also, the timing tree is constructed by timing-tree generation component. During assembly-code generation in compile time, the timing-tree generation traverses syntax tree and flow graph to create the timing tree for each procedure. The timing-tree nodes represent a program's sequential parts (basic blocks), branches, bounded loops, markers, and scopes. In the tree's leaves, the maximum timing information of the basic block (sequential part) is stored; from the leaves, timing information is generated by going up the scopes. If a marker, which is given by Modula-R language and limits loops in the marked range, is set, the marked range is defined as a scope and a timing-tree node.

The maximum time analysis component has several formulas. For example, maximum execution time of sequential contructs is the sum of all the constructs; maximum execution time of branch construct is (maximum execution time of condition statement) + (maximum value between (maximum execution time of alternative_1) and (maximum execution time of alternative_2)). According to this information, the maximum time information of each timing-tree node is calculated.

Finally, through the time editor, developers can see the timing information and edits it. To illustrate, for the code in Mars

if37

a < b1

then

proc1(a);36

else

proc2(a);24

endif;

the numbers of the right-hand side designates execution times according to the code's conditions. If a is smaller than b, proc1(a) will be called; since the maximum time of proc1(a) is 36 and the execution time of comparison of a and b is 1, one of the maximum value in this conditional code is 37. When a user changes the execution time into 20, the maximum value is modified into 25. This method is recommended to find bottle neck of an algorithm.

For PRET project, the timing analysis of Mars seems useful. In a PRET's application, every time we select a dead instruction, we can regard it as a node of the timing tree. If a task is an infinite loop and some scopes of the inside loop has to be cyclic, we can easily calculate how many cycles the scope will take by going up scope of the timing tree. Besides, if we use several dead instructions for each thread and each thread has to be synchronized, the timing information will be useful to figure out timing information affected by the synchronization. If a thread receives synchronization signals every x cycles from the other thread, it can be defined as a node of the timing tree. The timing effects by synchronizations can be simplified.

Goals of WCET analysis are to be safe and tight.

WCET of a piece of code depends on:

* Possible sequences of program actions

* Time taken by each of the actions.

The former is expressed more easily at the source code level, while the latter needs machine code. Thus, WCET analysis comprised of three problems:

* Characterization of execution paths

* Translation of path information from source code level to machine code level.

* Hardware-level execution-time analysis

Seems like, path characterization mostly relies on programmer annotations, with maybe some automatic support to aide the programmer. No reference cited for completely automatic path information extraction.

This paper utilizes the same idea as the previous decoupled architecture paper, with 2 processors. One being the Execute Processor, and one being the Access processor (memory access). THe paper doesn't go into a lot of details about the communication between them ,but it refers to a couple queues (such as load queues and store queues) to do the communication. Basically, they state that maybe for general purpose applications decoupled architecture doesn't work well because programs aren't structured in a way that can easily separate between memory access and computation, but for media applications, it is well structured. They compare against traditional SIMD machines and state that the amount of overhead for preparing SIMD instructions (packing, unpacking data etc) can be offset by the Decoupled architecture. For us, one thing we can take away is to evaluate whether a decoupled architecture makes sense for our applications. It seems that since we have interleave pipeline with multi threads, we could possible have the same effect with just one core? We should evaluate and learn more real time applications and see most of their memory access and execution code pattern.

detrimental to WCET analysis. They are defined as cases where

changing the timing of a single instruction in a stream of

instructions affects the timing of the overall stream by a larger

amount than the original change (or in the opposite direction). For

example, a case in which decreasing the latency of a single

instruction can decrease the latency of the overall instruction stream

by a larger amount is a timing anomaly. It would also be a timing

anomaly if decreasing the latency of the one instruction caused an

overall increase by any amount. There are straightforward and very

similar examples when the latency of a single instruction is

increased.

The authors present a previous analysis (T. Lundqvist and P.

Stenström, 1999) showing that allowing out-of-order execution could

cause timing anomalies, and present an example of this phenomenon that

is very similar in spirit to the proof of Richard's Anomalies (Richard

Graham, 1976). They then also show that disallowing out-of-order

execution is not enough to prevent timing anomalies by presenting an

example of a timing anomaly that can occur without out-of-order

execution.

They then present an alternative criterion, which is necessary but not

sufficient condition for the occurrence of timing anomalies. This

criterion is the possibility of resource allocation decisions, which

they define to be any choice that must be made in allocating hardware

such that a change to the latency of some instruction can change the

stream of instructions allocated to any functional unit. This

criterion is satisfied in situations where more than one piece of

hardware can perform the same function, because an increased latency

for one instruction can cause a following instruction to be allocated

to the other hardware unit.

The collected results are misleading. The instruction throughput compares MCGREP with openRISC and Microblaze without caches, MMU, and FPU and shows that MCGREP has reasonably good performance. The variability in execution times reintroduce the caches in openRISC and Microblaze and show that MCGREP has smaller variation in execution times. Then the authors continue to describe how microcode can be used to handle interrupts, atomic operations, and priority inheritance.