Team udvikler matematisk solver til analoge computere

Din computer udfører de fleste opgaver godt. Til tekstbehandling, visse beregninger, grafisk kunst og websurfing, den digitale boks på dit skrivebord er det bedste værktøj til jobbet. Men den måde, din computer fungerer på, med sin matematikstil, der er afhængig af det binære kodesystem med "on" og "off" 1s og 0s, er ikke ideel til at løse ethvert problem.

Derfor har forskere som Zoltán Toroczkai, professor i Institut for Fysik og samtidig professor i Institut for Datalogi og teknik ved University of Notre Dame, er interesseret i at genoplive analog computing på et tidspunkt, hvor digital computing har nået sit maksimale potentiale.

Toroczkai og samarbejdspartnere har arbejdet på at udvikle en ny matematisk tilgang, der vil hjælpe med at fremme beregning ud over de digitale rammer. Hans seneste papir, udgivet i Naturkommunikation , beskriver en ny matematik, analog "solver", der potentielt kan finde den bedste løsning på NP-hårde problemer.

NP-hårdhed er en teori om beregningskompleksitet, med problemer, der er berømte for deres vanskeligheder. Når antallet af variabler er stort, problemer forbundet med planlægning, proteinfoldning, bioinformatik, medicinsk billeddannelse og mange andre områder er næsten uløselige med kendte metoder. Efter at have testet deres nye metode på en række forskellige NP-hårde problemer, forskerne konkluderede, at deres solver har potentiale til at føre til bedre, og muligvis hurtigere, løsninger, der kan beregnes digitalt.

Analoge computere blev brugt til at forudsige tidevand fra begyndelsen til midten af ​​det 20. århundrede, guide våben på slagskibe og skyde NASAs første raketter ud i rummet. De brugte først gear og vakuumrør, og senere, transistorer, der kunne konfigureres til at løse problemer med en række variabler. De udfører matematiske funktioner direkte. For eksempel, for at tilføje 5 og 9, analoge computere tilføjer spændinger, der svarer til disse tal, og få straks det korrekte svar. Imidlertid, analoge computere var besværlige og tilbøjelige til "støj"-forstyrrelser i signalerne-og var svære at konfigurere igen for at løse forskellige problemer, så de faldt i unåde.

Digitale computere opstod efter at transistorer og integrerede kredsløb pålideligt blev masseproduceret, og for mange opgaver er de nøjagtige og tilstrækkeligt fleksible. Computeralgoritmer, i form af software, er sæt af instruktioner, der fortæller computerens hardware, hvordan de skal udføres. Fordi processen er begrænset til brug af 0'er og 1'er, dette gør også deres programmering enklere, og tillod digital computing at dominere i næsten 70 år.

Imidlertid, deres begrænsninger kan forhindre digitale computere i at løse NP-hårde problemer med mange variabler. Et sådant problem er "Traveling Salesman" -problemet, hvor en sælger skal starte i en by og vende tilbage til den by i slutningen af ​​en rejse, men imellem, skal rejse til alle de forskellige byer på en liste. Hvad er den mest effektive rute blandt alle punkterne? Problemet bliver eksponentielt mere udfordrende med tilføjelsen af ​​flere byer. Vanskeligheden med sådanne optimeringsproblemer, Toroczkai bemærkede, er "mens du altid kan komme med et svar, du kan ikke afgøre, om det er optimalt. At bestemme, at der ikke er en bedre løsning, er lige så svært som selve problemet. "

En udfordring for analog computing hviler på designet af kontinuerlige algoritmer. I modsætning til digital computing, som har en lang historie inden for algoritmeudvikling, algoritmer til analoge computere mangler en lignende vidensbase og er derfor meget vanskelige at designe. Toroczkais tilgang er forskellig fra algoritmetyperne til digitale computere, i alle aspekter.

Det næste trin er at designe og bygge enheder baseret på denne tilgang, en proces, der vil blive tacklet inden for Notre Dame's College of Engineering. De analoge computere ville være bygget til specifikke opgaver, og ikke til hverdagens computerbehov. Dette arbejde er en del af en større skala, multiinstitutionel indsats, kaldet ekstremt energieffektiv kollektiv elektronik (EXCEL), ledet af Notre Dame's Suman Datta, Freimann formand for teknik og professor i elektroteknik, i samarbejde med Sharon Hu, professor i datalogi og teknik.

"Der er for det meste ingeniørproblemer, der skal løses på dette tidspunkt, såsom falske kapaciteter og bedre støjkontrol, men det kommer derhen, "Toroczkai sagde." Ideelt set vil jeg gerne se, at du har denne boks på dit skrivebord, der er din planlægger. Og det kommer til at klare et meget bedre job end din almindelige computer. "