Complexity

Theory
1 / 65
 What is a Computer?
The handwaving explanation

EE 5332 2 / 65
 What is a Computer?
The handwaving explanation

Processing unit: capable of certain types of elementary operations

EE 5332 2 / 65
 What is a Computer?
The handwaving explanation

Processing unit: capable of certain types of elementary operations

Memory: storage -- includes registers files, external memory, disk

EE 5332 2 / 65
 What is a Computer?
The handwaving explanation

Processing unit: capable of certain types of elementary operations

Memory: storage -- includes registers files, external memory, disk

Program: Algorithm encoded in machine language

EE 5332 2 / 65
 What is a program?
Encode a sequence of steps in machine language
Machine language or Machine instructions: specific to processor
Instruction set architecture: core definition of machine
Assume ability to store variables, perform operations

EE 5332 3 / 65
 What is a program?
Encode a sequence of steps in machine language
Machine language or Machine instructions: specific to processor
Instruction set architecture: core definition of machine
Assume ability to store variables, perform operations

Elementary operations

Something that a computer can perform in unit time or constant time

EE 5332 3 / 65
 Example: sorting
23 5 97 42 15 1 36 58

EE 5332 4 / 65
 Example: sorting
Find smallest number

23 5 97 42 15 1 36 58

EE 5332 5 / 65
 Example: sorting
Find smallest number

23 5 97 42 15 1 36 58

EE 5332 6 / 65
 Example: sorting

23 5 97 42 15 1 36 58

EE 5332 7 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5

EE 5332 8 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5

EE 5332 9 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15

EE 5332 10 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15

EE 5332 11 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23

EE 5332 12 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23

EE 5332 13 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23 36

EE 5332 14 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23 36

EE 5332 15 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23 36 42

EE 5332 16 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23 36 42

EE 5332 17 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23 36 42 58

EE 5332 18 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23 36 42 58

EE 5332 19 / 65
 Example: sorting

23 5 97 42 15 1 36 58

1 5 15 23 36 42 58 97

EE 5332 20 / 65
 Algorithm
for(i=0; i<N; i++) {
// Scan for ith smallest number
min = INFINITY; minloc = -1;
for (j=0; j<N; j++) {
if ( (x[j] < min) && (! sorted[j]) ) {
// Store value and position
min = x[j]; minloc = j;
}
}
// insert into correct location
sorted[minloc] = true;
y[i] = x[minloc];
}

EE 5332 21 / 65
 Algorithm Elementary Operations
for(i=0; i<N; i++) {
// Scan for ith smallest number
min = INFINITY; minloc = -1;
for (j=0; j<N; j++) {
if ( (x[j] < min) && (! sorted[j]) ) {
// Store value and position
min = x[j]; minloc = j;
}
}
// insert into correct location
sorted[minloc] = true;
y[i] = x[minloc];
}

EE 5332 22 / 65
 Algorithm Complexity
for(i=0; i<N; i++) {
// Scan for ith smallest number
min = INFINITY; minloc = -1;
for (j=0; j<N; j++) {
if ( (x[j] < min) && (! sorted[j]) ) {
// Store value and position
min = x[j]; minloc = j;
}
}
// insert into correct location
sorted[minloc] = true;
y[i] = x[minloc];
}

EE 5332 23 / 65
 Algorithm complexity
Elementary operations take unit time
What is size of input?
How does running time grow with size of input?

EE 5332 24 / 65
 Algorithm complexity
Elementary operations take unit time
What is size of input?
How does running time grow with size of input?

Example: Sorting

input size: N (number of values to be sorted)

EE 5332 24 / 65
 Other algorithms possible

EE 5332 25 / 65
 Other algorithms possible
Insertion / Selection sort: O(N2)

EE 5332 25 / 65
 Other algorithms possible
Insertion / Selection sort: O(N2)

ick / Heap / Merge sort: O(N log N)

Different hidden constants - quicksort usually preferred in practice but has quadratic
worst case!

EE 5332 25 / 65
 icksort - recursive
N = 16

EE 5332 26 / 65
 icksort - recursive
N = 16

N=8 N=8

EE 5332 27 / 65
 icksort - recursive
N = 16

N=8 N=8

N=4 N=4 N=4 N=4

EE 5332 28 / 65
 icksort - recursive
N = 16

N=8 N=8

N=4 N=4 N=4 N=4

N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=2

EE 5332 29 / 65
 icksort - recursive
N = 16

N=8 N=8

N=4 N=4 N=4 N=4

N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

EE 5332 30 / 65
 icksort - recursive
N = 16

N=8 N=8

N=4 N=4 N=4 N=4

N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Nx1

EE 5332 31 / 65
 icksort - recursive
N = 16

N=8 N=8

N=4 N=4 N=4 N=4

N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=2 N/2 x 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Nx1

EE 5332 32 / 65
 icksort - recursive
N = 16

N=8 N=8

N=4 N=4 N=4 N=4 N/4 x 4

N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=2 N/2 x 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Nx1

EE 5332 33 / 65
 icksort - recursive
N = 16

N=8 N=8 N/8 x 8

N=4 N=4 N=4 N=4 N/4 x 4

N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=2 N/2 x 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Nx1

EE 5332 34 / 65
 icksort - recursive
N = 16 N/N x N

N=8 N=8 N/8 x 8

N=4 N=4 N=4 N=4 N/4 x 4

N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=2 N/2 x 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Nx1

EE 5332 35 / 65
 Other algorithms possible
Insertion / Selection sort: O(N2)

ick / Heap / Merge sort: O(N log N)

Different hidden constants - quicksort usually preferred in practice but has quadratic
worst case!

Check all permutations and select: O(N!) ~ O(NN)

EE 5332 36 / 65
 Graphs
pt
hu ca
es
ro
no
pl sv
fr fi ko
it
he
en da
de
ja
bg
nl
ar
tr id zh
uk
ru fa
cs

A B

S1

S2

C D
Figures: Wikipedia

EE 5332 37 / 65
 Graph terminology
Vertex (Node, Actor)
Edge (branch)
Directed / Undirected
Degree
Problem size:
N or V: number of vertices
Figures: Wikipedia E: number of edges
Combinations: eg: O(E log V)

EE 5332 38 / 65
 Paths and Cycles

EE 5332 39 / 65
 Paths and Cycles

EE 5332 39 / 65
 Paths and Cycles

EE 5332 39 / 65
 Paths and Cycles

EE 5332 39 / 65
 Paths and Cycles

EE 5332 39 / 65
 Paths and Cycles

EE 5332 39 / 65
 Paths and Cycles

EE 5332 39 / 65
 Paths and Cycles

EE 5332 39 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Graph Algorithms - Critical Path

EE 5332 40 / 65
 Critical Path - Algo
# G (V, E): Graph with V vertices, E edges
# S: set or linked list or array
for all v in G: dist[v] = 0
S = find_nodes_with_zero_indeg(G) // Initialize
for all u in S: dist[u] = delay(u)
while S not empty:
u = pop(S) # Extract one element
for all v in neighbours(u):
if dist[u] + delay(v) > dist[v]:
dist[v] = dist[u] + delay(v)
delete edge u-v
if indeg(v) == 0:
add v to S
# At end if V not empty there was a loop

EE 5332 41 / 65
 Critical Path - Algo
# G (V, E): Graph with V vertices, E edges
# S: set or linked list or array
for all v in G: dist[v] = 0
S = find_nodes_with_zero_indeg(G) // Initialize
for all u in S: dist[u] = delay(u)
while S not empty:
u = pop(S) # Extract one element
for all v in neighbours(u):
if dist[u] + delay(v) > dist[v]:
dist[v] = dist[u] + delay(v)
delete edge u-v
if indeg(v) == 0:
add v to S
# At end if V not empty there was a loop

EE 5332 42 / 65
 Critical Path - Algo
# G (V, E): Graph with V vertices, E edges
# S: set or linked list or array
for all v in G: dist[v] = 0
S = find_nodes_with_zero_indeg(G) // Initialize
for all u in S: dist[u] = delay(u)
while S not empty:
u = pop(S) # Extract one element
for all v in neighbours(u):
if dist[u] + delay(v) > dist[v]:
dist[v] = dist[u] + delay(v)
delete edge u-v
if indeg(v) == 0:
add v to S
# At end if V not empty there was a loop

EE 5332 43 / 65
 Critical Path - Algo
# G (V, E): Graph with V vertices, E edges
# S: set or linked list or array
for all v in G: dist[v] = 0
S = find_nodes_with_zero_indeg(G) // Initialize
for all u in S: dist[u] = delay(u)
while S not empty:
u = pop(S) # Extract one element
for all v in neighbours(u):
if dist[u] + delay(v) > dist[v]:
dist[v] = dist[u] + delay(v)
delete edge u-v
if indeg(v) == 0:
add v to S
# At end if V not empty there was a loop

EE 5332 44 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Graph Algorithms - Colouring

EE 5332 45 / 65
 Colouring - Heuristic
# G (V, E): Graph with V vertices, E edges
# V: copy of set/list of vertices
Vtmp = V
active = 1
while V not empty:
while Vtmp not empty:
u = pop(Vtmp) # Extract one element
colour[u] = active
for all v in neighbours(u):
delete v from Vtmp
delete u from V
Vtmp = V # Copy remaining elements back for next round
active +=1 # Next colour

EE 5332 46 / 65
 Colouring - Heuristic
# G (V, E): Graph with V vertices, E edges
# V: copy of set/list of vertices
Vtmp = V
active = 1
while V not empty:
while Vtmp not empty:
u = pop(Vtmp) # Extract one element
colour[u] = active
for all v in neighbours(u):
delete v from Vtmp
delete u from V
Vtmp = V # Copy remaining elements back for next round
active +=1 # Next colour

EE 5332 47 / 65
 Algorithms: Summary
Need basic understanding of algorithms to appreciate EDA problems
NOT the same as DSP Algorithms
Mainly interested in asymptotic complexity
Many graph theory concepts and algorithms used
Terminology

EE 5332 48 / 65
 Hard problems

EE 5332 49 / 65
 Hard problems
Multiple possible algorithms to solve a problem

EE 5332 49 / 65
 Hard problems
Multiple possible algorithms to solve a problem

Even the best has exponential complexity!

EE 5332 49 / 65
 Hard problems
Multiple possible algorithms to solve a problem

Even the best has exponential complexity!

Solution verification: given a candidate, can you verify the solution efficiently?

Guessing / non-deterministic computer can solve it!

EE 5332 49 / 65
 NP and P
P : class of problems that have known polynomial-time solutions
NP : Non-deterministic polynomial acceptable problems - superset of P

EE 5332 50 / 65
 NP and P
P : class of problems that have known polynomial-time solutions

NP : Non-deterministic polynomial acceptable problems - superset of P

Some problems in NP don't seem to have any polynomial solutions

EE 5332 50 / 65
 NP and P
P : class of problems that have known polynomial-time solutions

NP : Non-deterministic polynomial acceptable problems - superset of P

Some problems in NP don't seem to have any polynomial solutions

NP-hard: all problems in NP can be reduced to this problem

At least as hard as the hardest problems in NP! ⁇

EE 5332 50 / 65
 Why is this relevant?
Electronic Design Automation (EDA) - many optimization problems
Many involve searching large (exponential) design spaces
No known polynomial-time (efficient) algorithms

EE 5332 51 / 65
 Why is this relevant?
Electronic Design Automation (EDA) - many optimization problems
Many involve searching large (exponential) design spaces
No known polynomial-time (efficient) algorithms

Heuristics
common sense or similar algorithms
They are still algorithms (clear sequence of steps)
but no guarantee of optimality

EE 5332 51 / 65
Multi-objective
optimization
52 / 65
 Design space

EE 5332 53 / 65
 Design space
System parameters
Bandwidth, desired throughput, image size, desired recognition accuracy
Architecture parameters
Type of processor, number of processors
Amount and type of RAM
Bus connections, bandwidth
Floating point vs Fixed Point

EE 5332 53 / 65
 Design space
System parameters
Bandwidth, desired throughput, image size, desired recognition accuracy
Architecture parameters
Type of processor, number of processors
Amount and type of RAM
Bus connections, bandwidth
Floating point vs Fixed Point

Solution space
Multidimensional axes
Each architecture choice corresponds to one point
Each point has multiple cost metrics

EE 5332 53 / 65
 Metrics of Cost

EE 5332 54 / 65
 Metrics of Cost
Speed
Frequency
Latency
Time period

EE 5332 54 / 65
 Metrics of Cost
Speed
Frequency
Latency
Time period

Area
Area of Silicon die
Memory footprint
Number of chips to build a system
Peripheral components, integration

EE 5332 54 / 65
 Metrics of Cost
Speed
Frequency
Latency
Time period

Area
Area of Silicon die
Memory footprint
Number of chips to build a system
Peripheral components, integration

Power / Energy
Heat generation / dissipation
Baery life

EE 5332 54 / 65
 Metrics of Cost
Speed
Frequency
Latency
Time period

Area
Area of Silicon die
Memory footprint
Number of chips to build a system
Peripheral components, integration

Power / Energy
Heat generation / dissipation
Baery life

Rupee (Dollar/Yen/Yuan/Euro) cost

EE 5332 54 / 65
 Comparing implementations
Values measured in arbitrary / normalized units
Smaller the beer for all metrics (assume for now)

EE 5332 55 / 65
 Comparing implementations
Values measured in arbitrary / normalized units
Smaller the beer for all metrics (assume for now)

Solution 1

Time = 10
Area = 20
Power = 30

EE 5332 55 / 65
 Comparing implementations
Values measured in arbitrary / normalized units
Smaller the beer for all metrics (assume for now)

Solution 1 Solution 2

Time = 10 Time = 50
Area = 20 Area = 30
Power = 30 Power = 40

EE 5332 55 / 65
 Comparing implementations
Values measured in arbitrary / normalized units
Smaller the beer for all metrics (assume for now)

Solution 1 Solution 2 Solution 3

Time = 10 Time = 50 Time = 30

EE 5332 55 / 65
 Pareto-optimal front

EE 5332 56 / 65
 Pareto-optimal front

EE 5332 57 / 65
 Pareto-optimal front

EE 5332 58 / 65
 Pareto-optimal front

EE 5332 59 / 65
 Pareto-optimal front

EE 5332 60 / 65
 Pareto-optimal front

EE 5332 61 / 65
 Pareto-optimal front

EE 5332 62 / 65
 Pareto-optimal front

EE 5332 63 / 65
 Pareto-optimal front

EE 5332 64 / 65
 Pareto-optimal front

EE 5332 65 / 65