Каталитичните изчисления: как запълнената памет може да ускори работата на компютъра

Ново изследване показва, че дори запълненото хранилище може да бъде полезно.

Свикнали сме да мислим, че напълно запълнената памет не е полезна за компютрите. Ако хард дискът ви е пълен със снимки или други данни, това не може да ускори компютъра ви – очевиден факт, който не изисква доказателства.

Оказва се, че не всичко е толкова просто. През 2014 г. Лоф и колегите му откриват, че дори напълно заетата памет може да увеличи изчислителната мощ на компютъра. Този ефект беше наречен каталитично изчисление и днес тази концепция помага за решаването на фундаментални проблеми в компютърните науки. Съвсем наскоро тя даде възможност на учените да докажат, че обичайният подход за изследване на ролята на паметта в компютрите едва ли ще доведе до успех.

Колко малко памет е достатъчна?

Каталитичните изчисления се появяват като част от теорията на изчислителната сложност – област от информатиката, която изучава какви ресурси (време и памет) са необходими за решаването на различните задачи. Всички алгоритми могат да бъдат оценени по скоростта на изпълнение и количеството необходима памет. Според тези критерии учените разделят задачите на различни класове.

Най-известният клас – „Р“ – включва задачи, които могат да бъдат решени бързо, като например намиране на най-малкото число в даден списък или най-краткия път между две точки. Другият клас, „L“, изисква алгоритмите да използват минимално количество памет. Така например намирането на най-малкото число в един списък е възможно без съществено използване на памет, така че този проблем принадлежи към класа L. Остава обаче въпросът: може ли всеки проблем от „P“ да бъде решен, като се използва минимално количество памет?

Учените смятат, че отговорът е „не“, но за да се докаже това, е необходимо да се намери задача, която изисква повече памет, отколкото позволява клас L.

Задачата, която не се поддава

В края на 2000 г. Пиер Макензи и Стивън Кук, едни от пионерите на теорията на изчислителната сложност, предложиха такава задача. Те я нарекоха „задача за оценяване на двоичното дърво“. Същността ѝ се състои в това да се изчисли крайната стойност с помощта на поредица от междинни операции, организирани като турнирна мрежа. Различните алгоритми могат да решат този проблем по различни начини, но при всичките се налага да се съхраняват междинните резултати.

Учените са предположили, че този проблем е невъзможно да бъде решен с помощта на изключително малко количество памет. В своя статия от 2010 г. те доказаха, че всеки стандартен алгоритъм изисква твърде много памет, за да бъде от клас L.

Доказателството им обаче не изключва съществуването на необичайни алгоритми, които биха могли да използват едно и също място в паметта едновременно за съхраняване на данните и за извършване на изчисленията. Те бяха толкова сигурни, че такива алгоритми са невъзможни, че дори обявиха награда от $100 за този, който успее да докаже обратното.

Неочакваният пробив

Михал Куцки от Карловия университет в Прага се заинтересувал от този проблем и решил да го проучи. Търсенето му обаче довело до неочаквано откритие: той и колегите му открили, че дори напълно запълнената памет може да помогне при изчисленията, ако се промени начинът, по който тя се използва.

Изследователите показаха, че ако можете временно да промените някои от данните в паметта, без да променяте крайното ѝ състояние, това създава нов изчислителен ресурс. Тези техники са в основата на каталитичните изчисления .

Решен ли е проблемът с оценката на дървото?

През 2020 г. Джеймс Кук (синът на Стивън Кук) и Иън Мерц приложиха принципите на каталитичните изчисления към проблема за оценка на бинарните дървета и успяха да докажат, че той е решим с по-малко памет, отколкото се смяташе досега. Този резултат не само опроверга предишните теоретични предположения, но и даде възможност на Кук да спечели обещаните от баща му 100 долара.

Това обаче не е краят на историята. През 2023 г. Кук и Мерц разработиха нов алгоритъм, който допълнително намали използването на памет. Сега много учени предполагат, че проблемът за оценка на двоичните дървета все още е от клас L и доказването на това е само въпрос на време. Ако това се потвърди, една от ключовите хипотези в областта на изчислителната сложност ще се окаже погрешна, а каталитичните изчисления ще се превърнат във важен инструмент в по-нататъшните изследвания.

Какво следва

Каталитичните изчисления вече предизвикаха интереса на изследователите. Сега учените проучват как техниката може да бъде приложена в други области, включително квантовите изчисления, случайните алгоритми и техниките за съхранение на данни. Както отбелязва Макензи, „едва сега започваме да разбираме възможностите на тези методи и предстоят още много открития“.

Може би в бъдеще каталитичните изчисления ще помогнат за разработването на по-ефективни алгоритми, които могат да работят с ограничени ресурси на паметта, както и ще доведат до нови подходи в компютърните науки.