The Knowledge Frontier

Kompyuta na akili bandiaChapisho la awaliNadhariaDakika 3 za kusoma

DISKI ILIYOJAA ILIYOAZIMWA HUFANYA KOMPYUTA KUWA NA KASI ZAIDI

Matatizo mengine huhitaji muda kidogo lakini hula kumbukumbu nyingi, mengine ni kinyume chake. Kwa kazi chache za msingi, wananadharia wamethibitisha mipaka thabiti katika ubadilishanaji huu: ukiwa na kumbukumbu ndogo ya kufanyia kazi, huwezi kuwa na kasi. Makala mpya inaonyesha kwamba rasilimali ya ajabu, kumbukumbu ambayo tayari imejaa na lazima irudishwe ikiwa salama kabisa, inavunja mipaka hiyo.

Diski kuu iliyoazimwa

Kielelezo hiki kinaitwa ukokotoaji kichocheo (catalytic computing), kilichoanzishwa mwaka 2014 na Buhrman, Cleve, Koucký, Loff na Speelman. Algorithimu inapewa kumbukumbu safi ndogo sana, ya kiwango cha biti log n kwa ingizo lenye ukubwa n, pamoja na kumbukumbu chafu kubwa mno ambayo tayari imejaa data yoyote ambayo haikuichagua. Inaweza kutumia zote mbili itakavyo, lakini inaposimama, kila biti ya kumbukumbu chafu lazima iwe kama ilivyokuwa hasa.

Waandishi wanatumia taswira ya kawaida: unaazima diski kuu kubwa mno ya rafiki, iliyojaa kumbukumbu za kidijitali za thamani, ili kufanya hesabu. Hutaki kumpoteza rafiki, kwa hiyo unarejesha kila biti ukimaliza.

Mwanzoni kielelezo hiki kilikusudiwa kuthibitisha kwamba kumbukumbu kama hiyo haina faida. Kwa mantiki ya kawaida, ili kurejesha kila kitu lazima uhifadhi taarifa zote, kwa hiyo hupati nafasi yoyote. Kwa mshangao, kinyume chake ndicho kilichothibitika kuwa kweli: kumbukumbu iliyojaa inakuwezesha kutatua matatizo ambayo hakuna anayejua jinsi ya kuyatatua kwa kumbukumbu safi peke yake. Lakini matokeo hayo yalihusu nafasi, na algorithimu hizo zilikuwa za polepole kupita kiasi.

Kasi zaidi ya kile kilichothibitishwa kuwa kinawezekana

Adelmo Morrison Orozco, Nathan Sheffield na Ryan Williams (MIT) sasa wanaangalia kasi. Kwa kumbukumbu safi ya kiwango cha logarithimu na kiasi cha kipolinomia cha kumbukumbu iliyoazimwa, wanatoa algorithimu ambazo:

  • hupanga orodha na kukokotoa mageuzi ya Fourier ya kidiskreti (discrete Fourier transform) kwa muda n^(1+o(1)), unaokaribia kuwa wa mstari;
  • huzidisha matriki kwa muda n^(ω+o(1)), kwa kasi sawa na mbinu bora inayojulikana yenye kumbukumbu isiyo na kikomo.

Bila diski iliyoazimwa, imethibitishwa kwamba zao la muda na kumbukumbu lazima liwe angalau la kiwango cha n² kwa kupanga na kwa mageuzi ya Fourier, na n³ kwa kuzidisha matriki. Kwa hiyo algorithimu hizi kichocheo zinafikia kasi ambazo hakuna algorithimu ya kawaida yenye kumbukumbu ndogo inayoweza kufikia. Waandishi wanauita huu uthibitisho wa kwanza usio na masharti kwamba algorithimu kichocheo zinazishinda zile zisizo kichocheo.

Badilisha, soma, tendua

Kiungo muhimu ni ujanja mfupi wa kimchanganyiko (combinatorial). Tuseme algorithimu inaweza kubadilisha sehemu ya kumbukumbu iliyoazimwa kati ya thamani isiyojulikana τ na τ + x, ambapo x ndilo tokeo inalolihitaji. Katika jedwali kubwa la “msaidizi”, nalo pia limeazimwa, ongeza 1 kwenye seti ya visanduku vilivyochaguliwa kwa uangalifu. Kisanduku kilicho katika nafasi τ kinaongezeka kwa moja ikiwa na tu ikiwa x iko katika seti fulani iliyotolewa. Kisha endesha kila hatua kinyumenyume, na diski inakuwa kama ilivyokuwa, isipokuwa ile biti ya jibu uliyoitaka.

Kurundika ujanja huu tabaka kwa tabaka huwezesha kutathmini saketi zisizo na kina kwa haraka. Kisha waandishi wanaandika upya mitandao ya kupanga, mageuzi ya haraka ya Fourier na kuzidisha matriki kwa haraka kama saketi za aina hiyo. Kwa hesabu, ni tabaka zinazozidisha visivyojulikana viwili pekee ndizo zinazogharimu zaidi; tabaka za mstari tupu karibu hazina gharama.

Ulinganisho wa haki

Pingamizi moja: mipaka ya kawaida inadhani kwamba jibu huandikwa mara moja, kutoka kushoto kwenda kulia, kwenye utepe tofauti wa matokeo, ilhali algorithimu kichocheo huandika jibu lao ndani ya diski iliyoazimwa. Makala inashughulikia jambo hili. Waandishi wanaonyesha kwamba algorithimu zao zinaweza kuandika jibu katika mapito mawili juu ya utepe wa matokeo, na kwamba kwa algorithimu za kawaida mapito mawili hayasaidii zaidi ya pito moja. Kwa hiyo mipaka bado inatumika, na utengano unabaki. Pia wanathibitisha kwamba pito moja halitoshi hata ukiwa na diski iliyoazimwa: kupanga hapo kunagonga kizuizi kilekile cha n².

Orodha ndefu ya wanufaika

Zana hizohizo zinatoa algorithimu kichocheo za haraka za kuzidisha namba kamili kubwa na polinomia, kuhesabu pembetatu na kutafuta kliki (cliques) katika mitandao, kugundua njia na mizunguko, na kulinganisha ruwaza za maandishi zenye herufi-mbadala (wildcards). Muda wao wa utekelezaji unalingana, isipokuwa kwa vigezo vidogo, na algorithimu bora zinazojulikana zenye kumbukumbu yote zinayotaka. Katika kila hali, kumbukumbu iliyoazimwa bado lazima irudi kama ilivyokopeshwa hasa.