GEM5 example | configuration | commands | with Parsec

### configuration ###
cores: 8
CPU clock: 2GHz
Memory: 1GB
L1-Cache size: 64kB
L1-Cache associativity: 2
L2-Cache size: 256kB
L2-Cache associativity: 16

Parsec Benchmark: streamcluster

Parsec Benchmark size: simdev

###

GEM5 commands (run from gem5 directory):

0) download from [here] the script generator: writescripts.pl & the input set files.

1) run this script to create other scripts, using one of the available benches:

> ./writescripts.pl streamcluster 8

The results will be:

streamcluster_8c_simdev.rcS
streamcluster_8c_simlarge.rcS
streamcluster_8c_simmedium.rcS
streamcluster_8c_simsmall.rcS
streamcluster_8c_test.rcS

2) run the command which creates the configuration & run the generated streamcluster_8c_simdev.rcS script on it:

> ./build/ALPHA/gem5.opt --stats-file=test.out ./configs/example/fs.py --kernel=/localhome/yourUser/M5_system_ALPHA_small/binaries/vmlinux_2.6.27-gcc_4.3.4 --disk-image=/localhome/yourUser/M5_system_ALPHA_small/disks/linux-parsec-2-1-m5-with-test-inputs.img --cpu-clock=2GHz -n 8 --mem-size=1GB --caches --l1d_size=32kB --l1i_size=32kB --l1d_assoc=2 --l1i_assoc=2 --l2cache --l2_size=256kB --l2_assoc=16 --script=/localhome/yourUser/gem5/streamcluster_8c_simdev.rcS

The result of this script is ready in m5out/test.out

4) if you run the configuration without any script, the configuration will be created & you can connect to this computer via telnet, have access to a console and write whatever commands you like.

> ./build/ALPHA/gem5.opt --stats-file=test.out ./configs/example/fs.py --kernel=/localhome/yourUser/M5_system_ALPHA_small/binaries/vmlinux_2.6.27-gcc_4.3.4 --disk-image=/localhome/yourUser/M5_system_ALPHA_small/disks/linux-parsec-2-1-m5-with-test-inputs.img --cpu-clock=2GHz -n 8 --mem-size=1GB --caches --l1d_size=32kB --l1i_size=32kB --l1d_assoc=2 --l1i_assoc=2 --l2cache --l2_size=256kB --l2_assoc=16

Output:
.....
Listening for system connection on port 3456
...

> telnet localhost 3456

> ls

Optimal binary search tree (OBST)

Titlul problemei: Se dă un set de chei cu o probabilitate de accesare, să se creeze arborele binar optim de căutare astfel încât costul total / timpul mediu de accesare să fie minim.

Formule importante:

OBST(i,j) = min {OBST(i, r-1) + OBST(r+1,j) + ∑p[k]}, unde i ≤ r ≤ j and i ≤ k ≤ j

OBST(i,i) = p[i] și OBST(i,i-1) = 0 pentru oricare 1 ≤ i ≤ N

Costul final este OBST(1,N)
Reconstituirea se face în functie de r-ul ales pentru fiecare iterație a lui OBST, care reprezintă rădăcina arborelui sau sub-arborelui curent.

Și un program pentru rezolvarea în Python are următorul output:

Programul se poate descărca aici.

Înmulțirea în lanț a matricelor | Matrix chain multiplication

Programul se află aici.

0-1 Knapsack problem | Problema rucsacului, cu Programare dinamica

Implementarea în Python se află aici.

Local alignment of sequence

Aceasta postare este o continuare la Global alignment of DNA sequence, cu diferenta ca matricea de valori este initializata toata cu 0 (inclusiv marginile), iar valorile negative din matricea de costuri sunt rotunjite la 0.
Am considerat costurile:  match = 2, mismatch = -1, gap = -2

Prima matrice: costurile
A doua matrice: precedenta - 0 (diagonala), 1 (vine de sus), 2 (vine din stanga), -1 (neinitializat)

Sursa se afla aici.