Brza Furijeova transformacija je postala još brža

U svetu informatike (kao nauke) nema važnijeg algoritma od Furijeove transformacije, a stručnjaci sa MIT-a su našli načina da ga ubrzaju.

Furijeova transformacija je jedan od fundamentalnih koncepata u informatičkoj nauci. Ona predstavlja metod za prikazivanje ne regularnih signala – kao što je dinamička promena napona u žici koja povezuje  MP3 uređaj sa zvučnikom – kao kombinacija čistih učestanosti (frekvencija). Njena primena je univerzalna u obradi signala, a može se iskoristiti prilikom kompresije slike ili digitalnog audio zapisa. Sem toga, može pomoći u rešavanju diferencijalnih jednačina ili u praćenju dinamike tržišta i berze.

Tajna leži, u stvari, u algoritmu koji nazivamo brza Furijeova transformacija, razrađena šezdesetih godina 20. veka, koja omogućava brži račun Fourijeove transformacije, tako reći, u letu. Od kada je algoritam razvijen i ušao u primenu, pa sve do sadašnjeg trenutka, ljudi su se pitali da li je moguće osmisliti neki novi algoritam koji bi bio još brži.

Tokom januara meseca na simpozijumu Diskretnih algoritama (Symposium on Discrete Algorithms [SODA]), grupa istraživača sa MIT univerziteta je predstavila novi algoritam koji, u velikom broju praktičnih primena, poboljšava brzu Furijeovu transformaciju. Pod određenim uslovima, poboljšanje može biti značajno – desetostruko ubrzanje. Novi algoritam je posebno koristan prilikom kompresije digitalne slike. To bi omogućilo uređajima kao što je smartphone da bežičnim putem emituju video materijal, a da im taj proces ne iscrpi skoro svu energiju iz baterija ili da ne potroše mesečni Internet protok za mnogo kraće vreme.

Poput postojećeg starog algoritma, i novi radi sa digitalnim signalima. Digitalni signal je, niz brojeva – diskretan uzorak analognih signala, kao što je zvuk muzičkog instrumenta. Oba algoritma postojeći digitalni signal sa određenim brojem signala izražavaju (prikazuju) kao težinsku sumu (weighted sum) istog broja frekvencija.

Pojam težinski uz reč „suma“ proizilazi iz činjenice da neka vrednost, u ovom slučaju frekvencija ima veći udeo u konačnom rezultatu (veću „težinu“). Zaista, mnoge frekvencije imaju zanemarljivi udeo u konačnom rezultatu, pa ih slobodno možemo otpisati. Ovo je razlog zašto je Furijeova transformacija korisna prilikom kompresije digitalnih podataka. Blok od 8×8 piksela (piksel – 1 tačka na monitoru) se može posmatrati kao signal od 64 podataka ili kao suma od 64 različite frekvencije. Međutim, kao što istraživači pokazuju u svom skorašnjem radu, empirijska istraživanja pokazuju da, u proseku, možemo zanemariti 57 od tih 64 frekvencije. Sa druge strane, gubitak kvaliteta slike je minimalan.

Teško deljenje

Signali koje Furijeova transformacija formira na osnovu relativnog malo broja „teških“ frekvencija se nazivaju „sparse“ (oskudan). Novi algoritam „prepoznaje“ težinu najtežih frekvencija u signalu; što je signal oskudniji, to je veće ubrzanje koje algoritam daje. U krajnjem slučaju, ako je signal dovoljno oskudan, algoritam ga može interpretirati po principu slučajnog izobara, umesto da ga čita potpuno.

„U prirodi, većina normalnih signala su ’oskudni’.“ tvrdi Dina Katabi (Dina Katabi),  jedan od članova istraživačkog tima koji je razvio novi algoritam. „Razmotrimo, na primer, snimanje neke muzičke partiture kamerne muzike. Krajnji, kombinovani zvuk se sastoji od zvukova koje proizvode nekoliko instrumenata i to jednu notu u trenutku. Sa druge strane, snimanje svih mogućih instrumenata koji proizvode sve moguće zvukove u isto vreme ne bi bilo oskudno – ali to ne bi bio signal do koga je nekome stalo!“

Imajući ovo u vidu, kao neku vrstu definicije prirode signala oko nas, nastao je novi algoritam. Autori su profesori Katabi i Piotr Indyk, oboje sa MIT odseka koji se bavi kompjuterskom naukom i veštačkom inteligencijom. Uz njih, na istraživanju su radili i Erik Prajs (Eric Price) i Haitham Hasanej (Haitham Hassanieh), njihovi studenti. Novi algoritam se bazira na dva ključne ideje. Prva stvar je postojeći signal podeliti na uže propusne signale, i to tako da ti odsečci sadrže samo frekvencije sa velikom težinom.

Prilikom obrade signala, osnovni alat za izdvajanje frekvencije je filter. Međutim, filtri često imaju nejasne ili mutne granice. To znači da će određeni opseg frekvencija proći kroz filter, više manje ne promenjen, a frekvencije odmah van opsega filtera će biti prigušene. Što je veća razlika između opsega filtra i neke frekvencije, to će ona biti više prigušena. U krajnjem slučaju, neke frekvencije daleko od opsega neće uopšte proći i biće otklonjene zahvaljujući filtru.

Opisani princip rada filtra može dovesti do situacije gde će se neka od frekvencija sa velikom težinom naći na ivici opsega filtra i samim tim u situaciji da bude prigušena i zanemarena. Zbog toga, istraživači su morali naći efikasan način da kombinuju filtre sa različitim opsezima koji se preklapaju, sve sa ciljem da ni jedna teška frekvencija u ciljanom opsegu ne završi prigušena, ali da granice između isečaka i dalje ostanu dovoljno oštre.

Kada jednom izoluju neki segment spektra, istraživači su i dalje u poziciji da moraju odrediti koje su frekvencije najteže u datom delu. To su postigli učestalim seckanjem posmatranog dela spektra na manje delove i zadržavajući samo one gde je veći deo signala bio skoncentrisan. Za sada, prema radu koji je još neobjavljen,  istraživači opisuju znatno efikasniju tehniku, koja se oslanja na strategiju obrade signala koju koriste 4G telefonske mreže. Frekvencije se mogu posmatrati kao sitna talasanja, ali se zato mogu razmatrati kao oscilacije; obradom istog dela opsega ali u različitim trenucima vremena, istraživači mogu ustanoviti koja je frekvencija dominantna u određenom ciklusu oscilacije.

Istraživanje i rezultat koji sam upravo opisao nije prvo u ovoj oblasti. Dva istraživača sa univerziteta u Mičigenu (SAD), Ana Gilbert (Anna Gilbert) i Martin Štraus (Martin Štraus) su već ranije predložili algoritam koji bi ubrzao svemoguću brzu Furijeovu transformaciju. Međutim, njihov algoritam doprineo ubrzanju u znatno manjem broju slučajeva nego ovaj novi algoritam sa MIT-a. Možda je čak i bolji ali manju vrednost u primenjivanju, manja mu je težina. 😉

Poenta cele priče je – ako želite ubrzanje u domenu obrade podataka, imate dva moguća pristupa:

a) Napraviti još bolji i brži kompjuter koji će moći da se nosi sa još većom količinom podataka nego njegov prethodnik, a da pri tome ne gubite ni jedan jedini podatak

ili

 b) Da optimizujete procese do te mere gde će algoritmi nalaziti pravu i suštinsku informaciju, a sve ostalo proglasiti šumom i nepotrebnim.

Ovaj drugi pristup je definitvno brži, ali morate uvek imati na umu da se prilikom njegove primene može desiti neželjeni, vitalni gubitak informacije. Novi algoritam je tu i verovatno će naći svoju primenu, a koliko će nam pomoći u razvoju nauke i kompjutera, to će tek vreme pokazati.

 ***

U akustici, fizičke barijere, napravljene od čvrstih tela imaju tendenciju da odbijaju zvuk više frekvencije, a da propuštaju zvuk niže frekvencije. Kada se izvor zvuka ili muzike nalazi u susednoj sobi, slušalac će mnogo lakše čuti niže tonove od viših, pod uslovom da je između njega i izvora samo zid (bez ikakvih otvora).

 

Novi poluprovodnici će omogućiti razvoj prvih, pravih 3D čipova

Septembra meseca ove godine, kompanije 3M i IBM su najavile, da te dve firme planiranju da se udruže u razvijanju posebnog lepka, koji će omogućiti da se poluprovodnici gusto pakuju u silikonske „kule“ (pogledati video). Cilj im je da naprave nove tipove materijala, koji bi omogućili da se naprave, po prvi put, komercijalni mikroprocesori sastavljeni od 100 ravni. Svaka ravan bi sadržala po jedan čip.

Kompanije IMB i 3M, razvijaju novi tip „elektronskog lepka“ koji će se koristi za pravljenje „kule“ sastavljene od poluprovodnika – 3D čip. Lepak, prikazan plavom bojom na slici, povezuje čak do 100 odvojenih čipova, a u isto vreme izvlači toplotu koja se stvara u njima, prilikom operativne upotrebe. Ova inovacija bi mogla da dovede do proizvodnje mikroprocesora koji su i do 1000 puta jači od današnjih PC čipova.

Ovaj nivo „pakovanja“ bi omogućio dramatično veći nivo integracije ili rečeno prostije, kompjuteri bi mogli biti znatno manji i jači nego što je to, sada, slučaj. To bi, praktično, značilo da bi procesori bili gusto pakovani sa memorijom i mrežnim uređajima, u svojevrsne „blokove“ silikona. Ovi blokovi bi tada predstavljali i do 1000 puta brže kompjuterske čipove, nego što imamo danas. Jasno je da bi sa tim poboljšanjem dobili, celu paletu novih, bržih i jačih uređaja – PC kompjutere, tablet kompjutere, smartphone uređaje…

Ovaj proizvod bi mogao da doprinese velikom napretku u današnjim pokušajima da se procesori pakuju vertikalno – poznato kao 3D pakovanje. Sadašnja istraživanja se bore sa nezgodnim tehničkim problemima koja, u stvari, onemogućuju pravi prelaz na trodimenzionalnu formu čipova. Na primer, novi tip lepljivog sredstva mora obezbediti dobru provodnost toplote kroz gusto pakovanje čipova i da, u isto vreme, obezbedi odvođenje, te iste toplote, van osetljivih delova, kao što su logička kola.

„Današnji čipovi, u sebi imaju te ‘3D’ tranzistore, ali u suštini, to su i dalje 2D čipovi sa vrlo ravnom strukturom.“ kaže Bernard Mejerson (Bernard Meyerson), pod predsednik istraživačkog sektora u kompaniji IBM. „Naši naučnici ciljaju da razviju materijale koji bi nam omogućili da zapakujemo ogromnu količinu ‘kompjuterske snage’ u novu kompjutersku formu – silikonski ’neboder’. Verujemo da možemo napraviti napredak u nivou pakovanja, i da stvorimo novi tip, klasu poluprovodnika koji mogu ponuditi veće brzine i nove mogućnosti. Što je još važnije, energetski zahtevi takvih procesora bi i dalje ostali dovoljno niski. To predstavlja jedan od ključnih zahteva za mnoge proizvođače kompjuterske i elektronske opreme. Ovaj zahtev je posebno značajan prilikom projektovanja uređaja kao što je smartphone ili tablet kompjuter.“

Cilj je spojiti sve „oblande“

Mnogi tipovi poluprovodnika, uključujući i one koji se koriste za serverske čipove, danas, zahtevaju pakovanje i povezivanje koje se može primeniti samo na pojedinačne čipove. Kompanije 3M i IBM planiraju da razviju lepljive smese koje bi mogle da se primene na celovite silikonske „oblande“, povezujući stotine, možda, i na hiljade čipova.

Po dogovoru, IBM će iskoristiti svoje iskustvo da bi razvio jedinstvene procese pakovanja poluprovodnika, a 3M  bi obezbedio svoje znanje i resurse u razvijanju i proizvodnji lepljivih materijala.

„Iskorišćavanjem zajedničkog znanja i resursa, 3M je vrlo zainteresovan za saradnju sa kompanijom IBM – liderom u tehnologiji razvoja poluprovodnika,“ kaže Harv Gindre (Herve Gindre), pod predsednik 3M odseka koji se bavi elektronskim materijalima. „3M je, kao kompanija, sarađivala godinama unazad sa IBM-om, i ova nova saradnja, naš postojeći odnos diže na novi nivo. Vrlo nam je drago da smo integralni deo inicijative koja će ostvariti ovako naprednu tehnologiju 3D pakovanja.“

Lepljivi (athezivni) materijali predstavljaju jedan od 46 glavnih tehnoloških platformi razvoja u kompaniji 3M. Njihovi dosadašnji proizvodi su uvek bili precizno projektovani prema potrebama mušterija i sve prisutni su – možete ih naći u različitim oblastima, od proizvodnje poluprovodnika pa sve do materijala koji se prave za upotrebu u svemirskim istraživanjima i poduhvatima.

Ušteda goriva koristeći sistem koji se zasniva na korišćenju smartphone-a

Jula ove godine, Asocijacija pod imenom „Computing Machinery’s MobiSys“ je uručila nagradu za najbolji rad istraživačima sa MIT-a i univerziteta u Prinstonu za projekat sistema, koji koristi smartfon (smartphone) kao interfejs za prikupljanje informacija o stanju saobraćaja. Ceo koncept je osmišljen kao pomoć vozačima u gradskim gužvama i smanji čekanje na semaforima. Smanjivanjem praznog hoda i učestalosti ubrzavanja od stanja mirovanja, sistem je omogućio još jednu važnu stvar: prema testu koji je sproveden, vozači učesnici su smanjili potrošnju goriva za 20 procenata.

Izvor: Massachusetts Institute of Technology