Studoši

Charm fmst Prezentacija MAS-JK-3-5, slajdovi 21, 22, 23. Tamo se nalazi opisi postupka za 3SS, LOG i ORT. Za LOG i ORT su u oba slučaja uzeli s=d/2, tako da pretpostavljam da je to točno uvijek.

Dakle kako je napisao kolega Bobicki, ovo bi trebalo biti tako i stvar je riješena?
I koji je primjer s tim blokovima u docu riješen točno? (ako uopće postoji)

gama Jel se sigurno kod neparnog d (npr. d=5) zaokružuje na manji broj dok se dijeli s 2. Jel za d=5 => d/2 = 2.5 onda uzimamo 2 il 3?

Miskina666 Alen Duspara kaže da se radi cjelobrojno dijeljenje, tako da je 2.

A kod racunanja broja operacija, jel racunamo sve operacije iako su neke od njih za isti blok?
npr. izracunali smo MAD za neki blok i u sljedecem koraku trebamo za taj isti blok ponovno izracunati MAD.

Hoce obje operacije uci u konacni zbroj operacija ili uzimamo samo jednu od takvih.

fmst Ako je suditi po slici koja opisuje ORT, onda ih ne bi trebali ponovo uzimati u obzir, jer dolje u broj točaka za proračun samo dosad neviđene stavljaju

na ovo mislim:

gama to ima smisla jer je to ona tocka u koju smo se pomaknuli, ali ono sto me zanima je sto ako nam je u jednom koraku ta tocka bila recimo gore, a u sljedecem koraku lijevo.

Rekao bih da biraš ono tako da ti u najgorem slučaju min prozor bude na rubovima.

Npr. ako imaš 8×8 prozor s 2×2 blokom, d ti je 3, uzimaš \lfloor \frac{d + 1}{2} \rfloor jer u slučaju da ti je minimum odmaknut 2 , onda sljedeći gledaš odmaknut za 1, a to će ti biti rub prozora pretraživanja. U slučaju kad bi imao 9×9 s 2×2 prozorom, onda ti je d = 4, i tad opet možeš dobiti rub prozora s početnim s = 2, sljedeći s će biti 1, i opet worst case scenarij je rub (s one kraće strane).

Tako da moj guess je da mora vrijediti svojstvo da \sum{s_i} \leq d_{min}, a pošto vrijedi da je s_{i + 1} = \lfloor \frac{s_i}{2} \rfloor , onda ti s_{-1} mora biti d + 1 ili manje, pa je tako s_0 = \lfloor \frac{d_{min} + 1}{2} \rfloor kako bi osigurali da pregledavamo cijeli prozor.

Ako se radi o slučaju da smijemo popunjavati nulama, onda bi izraz bio s_0 = \lfloor \frac{d_{min} + 1}{2} \rfloor + (d_{max} - d_{min}). Time ćemo dobiti da provjeravamo cijeli prozor i u najgorem slučaju (npr. kad imamo asimetrične d-ove), a ako izađemo iz prozora lako samo kažemo da su to nul-blokovi. Ovo bi bio slučaj kad blok ne bi bio centriran (npr. kad su dimenzije prozora i bloka paran i neparan broj).

Tj ovo je bar moja logika koja se bazira na tome da nema apsolutno nikakvog smisla imati veći prozor pretraživanja za ORT i LOG ako nećeš potencijalno iskoristiti sve vrijednosti. A ako se kaže da je s_0 = \lfloor \frac{d}{2} \rfloor, onda za 8×8, 2×2 slučaj nikad nećeš pregledati dalje od okoline 1 bloka, dakle prozor bi ti komotno mogao biti 4×4 i ne bi bilo razlike u rezultatima.

M̵̧̩͑̀͝î̶͍̉ć̴̝̾́̀o̶̺̟̣͂̽ A kako znas jel d/2 ili (d+1)/2? S obzirom da je u predavanjima d/2

fmst vjerujem da se ne uzima, pogledaj ovdje:

zamagljeni su, a ni nema smisla nešto ponovo računati kad već znaš rezultat

adrian7000 Može biti i jedno i drugo, ali d + 1 ti daje rezultate koji bolje iskorištavaju vrijednosti, tj. dolaze bliže prozora. A znaš da mora biti d + 1 ili manje zato što u suprotnom imaš (skoro) geometrijski niz \frac{d}{2}+1 + \frac{d}{4} + \frac{d}{8} + ... čija suma je veća od d (teži u d + 1 za neke d-ove), i onda nije zadovoljeno \sum{s_i} \leq d_{min}.

MOD EDIT: Obrisao sam ono s d + 3 i d + 2 jer sam našao protuprimjere (npr. 14×14, 2×2). Znači ipak je d + 1 maksimum.

gama sjećam se iz ispita kod proračuna koliko su ORT i LOG efikasniji - ne uzima se, dakle jednom kad je neki blok izračunat više ga se ne računa - bilo da nam on treba odmah u sljedećem koraku ili 10 koraka nakon

Koliko zadataka obicno dode iz prvog dijela?

Kako se radi iz ulaznog u izlazni i suprotno…
kako se iz 5 dobije 1 ili pak iz 11 -> 3.

p444k zadano ti je da je q=4, tj kvantizacijski korak je 4, ulazni niz dijeliš s tim korakom

samo što su oni tu zaokruživali tipa 5/4=1.25 su stavili da je 1, a 11/4=2.75 su na 3, nama će biti ili ceil ili floor vjerujem

Pitanje, na MI-u su u podzadacima ORT i LOG pretrazivanja trazili da se jos nesto racuna, ne sjecam se tocno, mozda preciznost? Jel itko zna objasnit sta se trazilo i kako su se dobili oni brojevi jer samo znam da meni nisu ispadali pod ponudjenim.

renren
a)poboljsanje brzine izvodenja za oba algoritma u odnosu na full search –kako se računa to poboljšanje brzine izvođenja? broj operacija u full search/broj u ovim algoritmima
b)koliko iznosi mse ili mad u 2.koraku za desni blok
c)konacni vektor pomaka za oba algoritma

ovo je neko u doc napisao

jel formula za UKUPNO ubrzanje sa ona dva dijela: U = 1/(p1/N1 + p2/N2),
a za ubrzanje pojedinačnog dijela: U=1/(1-P+P/N) ?

p444k Da li za taj zadatak vrijedi ovo što je Zabe napisao?
Nije mi jasno što su radili u docu na tom zadatku.

Zabe Može neko potvrditi ove formule?

M
ože netko ovo iz dokumenta pojasnit? Što nije ako paralelno obrađujem podatke da vrjeme obrade bude kraće?

p444k pročitao sam negdje u tom docsu da se računa “vrijeme programa na procesoru”, tj. na svim jezgrama, što znači npr za 4000ns na 4 jezgre 4*1000ns, tj. opet 4000ns. Ne znam je li to točno doduše…

p444k Vrijeme obrade jednog podatka se ne mijenja, međutim obrada će biti prije završena jer je paralelizirana.