Graph Partitioning

Problem Search space is hugh:
- 2^V - 2 (for weighed nodes)
- reasoned by powerset
- V choose V/2 (for non-weighed nodes)


Partitioning is used to generate constraints for placement, as opposed to its original use for divide-and-conquer a problem. It's useful in placement where cells and wires are abstracted to nodes and edges. Delays are represented by weighs. The problem is formulated as partitioning a set of nodes into clusters of approx. equal size. The problem is known to be NP-complete. K&L's algorithm leverages heuristics to give good solutions.

Kernighan and Lin's algorithm:
Rely on gain calculation (for exchange a, b): g = Da - Db - 2*Cab, where Di = Ei (external cost) - Ii (internal cost). KL goes through a series of n exchanges, and chooses the culmulative gain maximum.
- O(n^2 log n)

Feduccia and Mattheyses
- claims O(n)


Multilevel scheme
1. Coarsening phase
2. Partitioning phase
3. Uncoarsening phase

- The main idea is that coarsening reduces the number of nodes and edges, which helps to speed up the partitioning alg.

- Collapsing vertexes into multinodes by matching
- Matching is not unique, so how do we find good matching?

Complex Theory

Good day for a little reading on complexity theories.

A complete problem is a representative problem for its class (e.g. NP-complete). All other problems within the class can be reduced to it.

NL
P
NP
PSPACE
EXPSPACE

Programming Paradigms for Dummies: What Every Programmer Should Know (Peter Van Roy)

Peter Van Roy. Programming Paradigms for Dummies: What EveryProgrammer Should Know, New Computational Paradigms for ComputerMusic, G. Assayag and A. Gerzso (eds.), IRCAM/Delatour France, 2009.
http://www.info.ucl.ac.be/~pvr/VanRoyChapter.pdf

Rate-Monotonic vs. EDF

Liu and Layland (1973) first discussed the max utilization for RM and EDF.

RM may have higher number of preemptions than EDF.

It has useful graphs for:
- execution load vs. # of preemptions
- # of tasks vs. # of preemptions

Jitter and Latency
- Control applications

Resource Sharing

Aperiodic Task

244 Timing Analysis

The basic clock cycle model is:

Tmax + Tsetup + Tskew + Tclk−to−Q ≤ T

- Tmax = time to propagate through the gates,

- Tsetup = time for signal to be stable within a cycle (before a clock tick)

- Tskew = mis-alignment of a clock signal to FF's

- Tclk-to-Q = time to change FF's output

in additional, there is the hold constraint:

Tmin ≥ Thold + Tskew

- Thold = time for signal to be stable within a cycle (after a clock tick). This says we have to hold the input signals to FFs for a while after a clock tick.

Tsetup is how fast a FF can operate (sufficient condition). Thold is the minimum time a FF need to operate (necessary condition). If Tsetup ≥ Thold, then we can ignore Thold.

Timing analysis helps to automatically infer the clock cycle time to run the circuit. It needs to model delay for wires and gates.