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).

 

Koliko košta besplatni Gmail, YouTube i Google pretraga?

Svaki put, kada neko od nas, iskoristi Google pretragu na Interentu, pogleda video na You Tube sajtu ili pošalje poruku koristeći Gmail, kompjuteri koji pripadaju kompaniji Google koriste električnu energiju. Raspoređeni po celom svetu po informatičkim centrima, oni, svi zajedno konstatno troše 260 milona vati u jedinici vremena, što predstavlja oko jedne četvrtine prinosa jedne prosečne nuklearne elektrane.

Izvor: Flickr

Izvor: New York Times

 

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.

Jolt – program koji je trebao da se pojavi ranije

Naučnici i istraživači sa univerziteta MIT su vrlo predani svakom poslu za koji se uhvate. Da je važno imati konkretne rezultate, to uvek stoji, ali nekada je problem imati bilo kakve rezultate.

Kada vas kompjuter izda i kada gledate kako višečasovni rad pred vama nestaje i odlazi u zaborav, jer se mašina ispred vas “zbunila”, tada počinje da vas prožima nagla i prekomerna nervoza i nazadovoljstvo. Kompjuter je ušao u beskonačnu petlju, nema šanse da ga izvučete i jedini način da nastavite sa radom jeste da restartujete aplikaciju ili još gore, kompjuter… i da izgubite sve što se radili od posledenje akcije snimanja dokumenta.

Neki ovo smatraju napornom činjenicom koju čovek mora prihvatiti kada radi sa mašinama, drugi imaju osećaj da se duh mašine okrenuo protiv njih, dok oni ekstremni naprave još veću štetu u napadu slepog besa i nezadovoljstva.

Rešenje ovakve situacije je aplikacija koja je u stanju da izvuče druge apikacije iz mrtve, beskonačne petlje izvršavanja jedne te iste instrukcije. Da, učenjaci sa MIT-a su se pozabavili problemom i dali svoj doprinos u borbi protiv nervoze nastale zbog izgubljenog truda.

Zamislimo situaciju u kojoj imamo kompjuter koji izlgeda kao da se baš dubko zamilio. Naravno, ako ste u mogućnosti da to uradite, startujete Jolt i on počinje sa pregledanjem i skeniranjem memorije. Sve što ova aplikacija radi, jeste provera da li dolazi do neke promene pošto se izvrši neka instrukcija. Ako je to slučaj, onda kompjuter, ipak, radi nešto korisno, u suprotnom imam slučaj bekonačnog izvršavanja jedne te iste instrkucije ili komande. Naš dragi spasitelj onda traži prvu sledeću instrukciju koja sledi posle koda u koji je naš kompjuter beznadežno upao. Jednom nađena, Jolt će naterati aplikaciju da pređe na njeno izvršavanje, što bi znašilo ujedno i izlazak iz petlje smrti.

Autori ovog softverskog pomagala ne garatuju da će se aplikacija potpuno opraviti posle ovakve intervencije. Tačnije, ne mogu da garantuju da će otrežnjena aplikacija imati sve funkcionalnosti, kao pre nemilog događaja, ali se odgovorno tvrdi da će korisnik biti u mogućnosti da sačuva svoj rad i da ugasi aplikaciju. Više nego dovoljno.

Šta se dešava kada Jolt upadne u duboko razmišljanje?

Kvantno znanje hladi kompjutere: novi način razumevanja entropije

Kompjuteri prilikom rada, stvaraju toplotu, i to je svima poznato. Ta činjenica se nije promenila od pojave prvog personalnog računara, ali ima nagoveštaja da se i to može promeniti. Članak bi lako mogao proći kao inženjerska priča da nije teorijskih fizičara. Oni su ti koji tvrde da se efekat zagrevanja prilikom rada kompjutera može pretvoriti u suprotni fenomen – u proces hlađenja. Iza ovakve tvrdnje stoji fundamentalno razmatranje koje se bavi stanjima posedovanja znanja i ne posedovanja znanja. Da ne bismo došli u situaciju da radimo na brzinu, objasnimo sve od samog početka…

Zasmislite da vam ne treba ni komad rashaldnog uređaja dok rade...

Prilikom rada kompjutera, energija koju oni koriste, pre ili kasnije, završi u obliku toplote. Fizičari kažu da to nije sve, kada je ovaj proces u pitanju, i imaju svoj komentar o osnovama potrošnje energije prilikom obrade informacija, podataka.

Skorašnje istraživanje, koje je sproveo tim fizičara, je dalo iznenađujući rezultat na, tom, osnovnom nivou. Profesor Renato Rener (Renato Renner) i Vlatko Vedral (Vlatko Vedral) iz centra za kvantnu tehnologiju pri Nacionalnom univerzitetu u Singapuru i pri Oksfordskom univerzitetu iz Velike Britanije i njihove kolege, opisuju kako brisanje podataka, u određenim uslovima može stvoriti efekat hlađenja, umesto zagrevanja. Efekat je kvantne prirode i nazivaju ga efektom vezivanja (entanglement). Kao krajnji rezultat ovog efekta može biti da super kompjuteri budućnosti imaju koristi od ovog kvantnog efekta u obliku konstantnog hlađenja, i samim tim dizanja performansi. Treba imati na umu da bi današnji kompjuteri bili još efikasniji (brži) da ne moramo da brinemo o njihovom zagrevanju. Ako ono pređe određene granice, kompjuter se jednostavno pregreva i u krajnjem ishodu, pregori.

„Postići kontrolu procesa hlađenja/zagrevanja na kvantnom nivou bi tražilo da se napravi veliki tehnološki skok, ali nije i nemoguće. Svedoci smo velikog napretka u polju kvantne tehnologije u poslednjih 20 godina.“ Kaže Vedral. Sa današnjim mogućnostima koje nudi savremena kvantna laboratorija, trebalo bi da je izvodljivo sprovesti bazični eksperiment, nad nekoliko bitova podataka.

Landauer-ov princip sa kvantnom začkoljicom

Fizičar Rolf Landauer (Rolf William Landauer) je izračunao još 1961. godine, da je tokom brisanja podataka oslobađanje toplote neizbežno. Po Landauer-ovom principu kada kompjuter, tokom rada, premaši neki broj operacija i jedinici vremena, stvorena toplota je tolika da se više ne može „izgubiti“. To, tačnije, znači da se brže generiše dodatna toplotna energija, nego što je sistem preda okolini. Kod današnjih super kompjutera, postoje i drugi izvori zagrevanja koji su značajni, ali Renner misli da će pomenuti efekat biti važan činilac za 10 ili 20 godina. Brojke kažu sledeće: Emisija toplote prilikom brisanja 10 terabajta (terabyte) je oko 1 milionitog dela 1 džula (joule). Međutim ako se ovakav proces brisanja ponovo veliki broj puta tokom jedne sekunde, onda zbirna toplota postaje značajna.

Novo istraživanje Launderovog principa se bavi slučajevima kada su vrednosti bitova koji se brišu poznate. Ako je memorijski sadržaj poznat, moguće ga je obrisati na takav način da ga je posle moguće stvoriti. Već je pokazano da ovo „povratno“ brisanje ne proizvodi toplotu. Sa novom studijom, istraživači idu korak dalje. Oni pokazuju sledeće: prilikom brisanja bitova informacija koje su vezane kvantno-mehanički sa posmatračem, sam posmatrač bi mogao da izvuče postojeću toplotu iz sistema. Kvantno vezivanje povezuje stanje posmatrača sa stanjem kompjutera na način koji ima omogućava da znaju više o memoriji nego da koriste pristup klasične fizike.

Slične formule – dve discipline

Da bi stigli do željenog rezultata (hlađenje tokom brisanja), naučnici kombinuju ideje iz informatičke teorije i koncept iz termodinamike poznat kao entropija. Ovaj pojam se pojavljuje u obe naučne discipline. Kod informatičke teorije entropija predstavlja meru gustine informacija. Takva, opisuje, na primer, koliko memorijskog kapaciteta bi zauzeo neki set podataka kao bi se optimalno kompresovao. U termodinamici, entropija je vezana za ne uređenost sistema. Ona definiše organizovanost molekula u gasu. Po termodinamici, dodavanje entropije sistemu znači dodavanje energije u obliku toplote.

Rener tvrdi: „Pokazalo se, o oba slučaja, da pojam entropije, u stvari, opisuje istu stvar, čak i u kvantno mehaničkom režimu.“  Kako formule za obe entropije imaju isti oblik, već se pretpostavljalo da postoji neka veza između njih. „Naša studija pokazuje, u oba slučaja, da se entropija može sagledati kao manjak znanja.“, ističe Rener.

Treba imati na umu, da prilikom merenja entropije nekog objekta, sam objekat nema entropiju kao takav. Umesto toga, entropija tog objekta je uvek zavisna od posmatrača. Ovo primenjeno na primer sa brisanjem podataka bi mogao dati sledeće. Ako dva nezavisna posmatrača (osobe) brišu podatak iz memorije i jedan od njih ima veću spoznaju o podatku od drugog posmatrača, tada, po njemu, podatak ima manju entropiju i on može obrisati podatke ulažući manju količinu energije. Sem toga, entropija ima neobičnu osobinu da može imati negativnu vrednost kada se posmatra iz ugla informatičke teorije. Potpuna, klasična spoznaja o sistemu znači da posmatrač vidi sistem sa entropijom čija je vrednost nula. Međutim, kvantno vezivanje, daje posmatraču „više nego kompletno znanje“, jer su kvantne korelacije jače od klasičnih. To nas, na posletku, vodi ka entropiji koja je manja od nule. Sve do sada, teoretski fizičari su koristili negativnu entropiju u svojim proračunima, bez dubljeg razumevanja šta bi ona mogla da znači u termodinamici ili u eksperimentu.

Nema zagrevanja, čak i hladi

Da sumiramo, malo.

U slučaju klasičnog, potpunog poznavanja kompjuterske memorije (entropija je nula vrednost), brisanje podatka, u teoriji ne zahteva bilo kakvo ulaganje energije.

U slučaju kvantnog vezivanja „više nego kompletno saznanje“ o memoriji (negativna entropija) vodi ka ta tome, da brisanje podataka dovodi ka izvlačenju topote iz sistema u obliku upotrebljive energije. Ovo bi bio fizički smisao negativne entropije.

Međutim,  Rener ističe: „Ovo ne znači da možemo da razvijemo perpetual mobile mašinu.“ To bi bila mašina iz snova koja bi proizvodila više energije nego što potroši, ili bi proizvodila koristan rad u beskonačnost, kada se jednom pokrene. U primeru sa brisanjem, podaci bi bili obrisani samo jednom, tako da nema mogućnosti da se dalje proizvodi energija. Sam proces, takođe, uništava kvantno vezivanje, i potreban je unos energije da bi se stanje sistema vratilo na početno. Jednačine koje opisuju ovaj proces su u saglasnosti sa drugim zakonom termodinamike: idja o tome da entropija univerzuma se ne može smanjivati, nikada. Vedral ističe: „U našoj studiji, operišemo na samoj granici drugog zakona. Ako krenemo dalje, prekršićemo ga.“

Osnovne pronalaska

Ova nova naučna istraživanja o entropiji mogu imati primene i van proračuna toplote koju kompjuteri proizvedu. Na primer, metode razvijene unutar informatičke teorije (one koje se tiču entropije) mogu dovesti do inovacija u termodinamici. Ovo bi predstavljalo svojevrsnu sinergiju između dve naučne discipline, koje na prvi pogled nemaju puno zajedničkog. Veza između dva koncepta je osnovna, fundamentalna.

Vreme će pokazati da li je ovaj put razmatranje entropije svojevrsni naučni pomak ili samo još jedna od naučnih stramputica. Jedno je sigurno: konačni rezultat ovakvog istraživanja možemo očekivati za vreme jednog životnoga doba. To je, i dalje, dovoljno vremena da se neko seti još boljeg načina da se kompjuteri hlade tokom njihovog rada, pa će ova kvantno mehanička varijanta postati – nepotrebna.