Два слова о трехзначной логике. Как работают троичные компьютеры и чем они интересны

Компь­юте­ры, исполь­зующие тро­ичную логику, при­дума­ны уже дав­но. Еще в 1958 году Н. П. Бру­сен­цов пос­тро­ил в МГУ пер­вую опыт­ную элек­трон­ную тро­ичную ЭВМ «Сетунь», а в 1973 году в США был соз­дан Ternac — экспе­римен­таль­ный тро­ичный эму­лятор с ариф­метикой над 24-трит­ными целыми и 48-трит­ными дей­стви­тель­ными чис­лами на дво­ичном компь­юте­ре Burroughs B1700. Может ли най­ти при­мене­ние тро­ичная логика в сов­ремен­ных компь­юте­рах? Крис Кас­пер­ски счи­тал, что это впол­не воз­можно!

INFO

Эта статья была слу­чай­но обна­руже­на в пыль­ном и порос­шем паути­ной чулане редак­ции «Хакера» во вре­мя оче­ред­ной генераль­ной убор­ки. Крис Кас­пер­ски написал ее еще в 2003 году, но по опре­делен­ным при­чинам матери­ал не был опуб­ликован. Сей­час мы решили испра­вить это. В сво­ем эссе Крис пытал­ся уга­дать сле­дующий шаг раз­вития вычис­литель­ной тех­ники и обра­тил свой взгляд на тро­ичную логику, которая, по его мне­нию, мог­ла бы стать осно­вой оче­ред­ного эта­па эво­люции высоких тех­нологий. Тех­ничес­кие под­робнос­ти, каса­ющиеся прин­ципов такой архи­тек­туры, не утра­тили акту­аль­нос­ти и сегод­ня.

Не­дале­кое будущее… Гиган­ты мик­ропро­цес­сорной индус­трии, как никог­да, оза­боче­ны бли­зостью физичес­ких огра­ниче­ний так­товой час­тоты и сте­пени интегра­ции, за которы­ми устой­чивую работу чипов гаран­тировать ста­нет прос­то невоз­можно. Про­изво­дитель­нос­ти же име­ющих­ся про­цес­соров, даже таких сприн­теров, как Pentium-XXX, хва­тит от силы года эдак на три, пос­ле чего пот­ребитель нач­нет шиб­ко нер­вни­чать и пинать кон­курен­тов, которые, вос­поль­зовав­шись все­общим замеша­тель­ством, получат шанс выр­вать­ся впе­ред. В ход идут все­воз­можные обходные при­емы уве­личе­ния про­изво­дитель­нос­ти — рас­парал­лелива­ние вычис­лений, упрежда­ющие исполне­ние и заг­рузка команд.

При­меча­тель­но, что вышепе­речис­ленные «новей­шие» дос­тижения не явля­ются новей­шими в бук­валь­ном понима­нии это­го сло­ва — в той или иной фор­ме они были реали­зова­ны еще на лам­повых машинах, нехило работа­ющих в куда более тес­ных рам­ках физичес­ких огра­ниче­ний. Быс­тро­дей­ствие и количес­тво элек­трон­ных ламп в пер­вых ЭВМ, конеч­но, не идет ни в какое срав­нение с чис­лом и рез­востью тран­зисто­ров в сов­ремен­ных компь­юте­рах, но тем не менее факт оста­ется фак­том.

Пос­тепен­но все эти тех­нологии миг­рирова­ли на плат­форму бытовых мик­ропро­цес­соров, мно­гок­ратно уве­личи­вая про­изво­дитель­ность, ког­да, казалось бы, все ресур­сы уже на исхо­де. Так про­изош­ло и на этот раз… Едва начали раз­давать­ся голоса, что конец золото­го века мик­ропро­цес­соров сов­сем бли­зок и пора начинать переби­рать­ся на клас­терные супер­компь­юте­ры, Intel «неожи­дан­но» вспом­нила о трех­знач­ной логике.

Но что же это такое — трех­знач­ная логика? И почему она сулит рекор­дное уве­личе­ние про­изво­дитель­нос­ти при нез­начитель­ном уве­личе­нии аппа­рат­ной слож­ности мик­ропро­цес­сора?

В соз­нании обы­вате­ля компь­юте­ры нас­толь­ко тес­но свя­заны с логикой дво­ичной, битами и бай­тами, что пред­ста­вить что‑то дру­гое боль­шинс­тво из нас прос­то не в сос­тоянии. На самом деле трех­знач­ная логика не нова, и впер­вые она была пос­тро­ена Лукасе­вичем в 1920 году! (Редак­тор заметил мимохо­дом, что три­логи­ка в какой‑то мере исполь­зовалась в машине Бэб­биджа, раз­работан­ной в XIX веке. Арис­тотель же обра­тил на нее вни­мание еще рань­ше. Одна­ко матема­тичес­ки осмысле­на три­логи­ка была лишь в середи­не XX века.) Как мож­но зак­лючить из наз­вания, в ней фигури­рует уже не два тер­ма: ис­тина и ложь, а три — ис­тина, ложь и фиг его зна­ет. Покажем пре­иму­щес­тва такого новов­ведения на прос­том при­мере.

Спро­си пер­вого встреч­ного «В Баг­даде сегод­ня был дождь?». С точ­ки зре­ния дво­ичной логики про­хожий дол­жен отве­тить либо «да», либо «нет». Но ни тот ни дру­гой ответ воп­роша­емый дать не может, пос­коль­ку он вам не мете­обю­ро. Ну не зна­ет он! Да невоз­можно это ска­зать язы­ком дво­ичной логики. При­дет­ся нам изме­нить воп­рос. Для начала поин­тересу­емся — «зна­ете ли вы сегод­ня погоду в Баг­даде?», и толь­ко в слу­чае утверди­тель­ного отве­та зададим сле­дующий воп­рос.

В тро­ичной логике ответ на наш воп­рос может быть получен сра­зу, то есть, говоря язы­ком кибер­нетики, за один такт работы про­цес­сора вмес­то двух: про­хожий отве­тит «А фиг его зна­ет!». Раз уж мы загово­рили о про­цес­сорах, рас­смот­рим прос­тей­шую прог­рам­мную задачу: срав­ним два чис­ла — А и В. Оче­вид­но, что воз­можны три вари­анта: A > B, A = B и A < B. В дво­ичном про­цес­соре эту опе­рацию при­ходит­ся осу­щест­влять за два про­хода. Сна­чала выяс­няем, рав­ны ли А и В. Если они ока­жут­ся нерав­ны, то вто­рым заходом уточ­няем, А боль­ше B или нет. Наг­лядно это показа­но на сле­дующем рисун­ке.

По­чему же компь­юте­ры до сих пор стро­ятся на дво­ичной осно­ве? При­чина зак­люча­ется в аппа­рат­ной прос­тоте дво­ичных вен­тилей. На опре­делен­ном эта­пе раз­вития вычис­литель­ной тех­ники бинар­ная логика ока­зыва­лась нам­ного выгод­нее и эко­номич­нее! Сегод­ня же все изме­нилось. Слож­ность вен­тилей ста­ла менее кри­тич­на их чис­ла и количес­тва соеди­нений меж­ду ними. А про­изво­дитель­ность и вов­се важ­нее все­го! Таким обра­зом, тро­ичные вен­тили выг­лядят весь­ма заман­чивым фун­дамен­том для сов­ремен­ных компь­юте­ров.

Ос­танав­лива­ет лишь пол­ная иде­оло­гичес­кая несов­мести­мость со ста­рыми моделя­ми. Все мы при­вык­ли, что память компь­юте­ров изме­ряет­ся бай­тами, а сами бай­ты сос­тоят из вось­ми битов. В свою оче­редь, каж­дый бит может при­нимать зна­чения ноль или один, соот­ветс­тву­ющие уров­ням сиг­нала на вхо­де логичес­кого эле­мен­та. В тро­ичной все не так. Там мерилом все­го ста­новит­ся трит, при­нима­ющий зна­чения –1, 0, +1, соот­ветс­тву­ющие уров­ням элек­три­чес­ких сиг­налов — отри­цатель­ный сиг­нал, нет сиг­нала, положи­тель­ный сиг­нал.

Шес­терка три­тов обра­зует ана­лог бай­та — трайт. Меж­ду про­чим, трайт име­ет прак­тичес­ки ту же аппа­рат­ную слож­ность, что и байт, но может хра­нить в себе не 28 = 256 целочис­ленных зна­чений, а 36 = 729 (!). Если речь идет о динами­чес­кой памяти, осно­ван­ной на трех­ста­биль­ных зарядо­вых эле­мен­тах — кон­денса­торах, то трайт будет про­ще бай­та, пос­коль­ку исполь­зует шесть, а не восемь яче­ек. Трех­ста­биль­ные триг­геры ста­тичес­кой памяти будут в 1,5 раза слож­нее, но за счет исполь­зования мень­шего чис­ла яче­ек получа­ем, что 9/6 * 6/8 = 1,125, трайт ста­тичес­кой памяти будет в гру­бом приб­лижении не слож­нее бай­та. Не прав­да ли, хороший спо­соб получить боль­ше опе­ратив­ной памяти за ту же цену? А ее более ком­пак­тное пред­став­ление авто­мати­чес­ки уве­личит ско­рость обме­на! Поэто­му сум­марный при­рост про­изво­дитель­нос­ти получа­ется весь­ма и весь­ма впе­чат­ляющим.

Но на самом же деле это толь­ко над­водная часть айсбер­га. Прак­тичес­кий при­рост про­изво­дитель­нос­ти про­изой­дет сов­сем по иным при­чинам. Что­бы понять это, вспом­ним теорию пред­став­ления чисел. В любой книж­ке по информа­тике мож­но про­честь стро­ки вро­де «...пред­став­лени­ем чис­ла N назовем такое пред­став­ление в позици­онной сис­теме исчисле­ния с положи­тель­ным целым осно­вани­ем p, при котором запись чис­ла в виде ряда цифр a1,a2,…an конеч­ной дли­ны n однознач­но опре­деля­ет зна­чение это­го чис­ла по фор­муле»

N = a1pn – 1 + a2pn – 2 + an-1p1 + ... + an

Фор­мула эта была проч­но вби­та в школь­ные годы учи­теля­ми информа­тики или же нем­ногим поз­же пре­пода­вате­лями — в сту­ден­ческие. Но в исчисле­нии с дво­ичным осно­вани­ем никаких прег­рад нет толь­ко на пер­вый взгляд (прав­да, об этом пытались умал­чивать, дабы не трав­мировать наше неж­ное юно­шес­кое соз­нание). Поп­робуй­те пред­ста­вить по такой фор­муле отри­цатель­ное чис­ло. Черт возь­ми, ока­зыва­ется, что это невоз­можно! В нашем арсе­нале толь­ко еди­ницы и нули, дающие лишь мно­жес­тво положи­тель­ных чисел и ноль в при­дачу.

Мож­но поразить­ся, как же ухит­ряет­ся работать сов­ремен­ный про­цес­сор. И в самом деле, как? Подумав некото­рое вре­мя, мы при­дем к выводу, что мож­но «выделить» один бит для ука­зания зна­ка чис­ла. Дей­стви­тель­но, имен­но так и устро­ено подав­ляющее боль­шинс­тво сов­ремен­ных про­цес­соров. Нап­ример, в чипах Intel стар­ший бит каж­дого чис­ла может интер­пре­тиро­вать­ся как зна­ковый. «Может» сле­дует читать и понимать в бук­валь­ном смыс­ле. Отли­чить зна­ковое чис­ло от без­зна­ково­го аппа­рат­но невоз­можно, так они име­ют иден­тичные пред­став­ления. При­ходит­ся «догова­ривать­ся» об этом заранее.

В самом деле, пос­мотрим, что про­исхо­дит, ког­да про­цес­сор пыта­ется отнять от еди­ницы двой­ку. Для начала про­цес­сор опре­деля­ет, какое чис­ло из двух боль­шее. В нашем слу­чае 1 < 2, поэто­му он меня­ет их мес­тами, уста­нав­лива­ет флаг перено­са, ком­пенси­руя изме­нение зна­ка, и побит­но отни­мает от еди­ницы раз­ность этих чисел. Это же сколь­ко мик­роопе­раций?! Хорошо, что хоть боль­шую часть работы про­цес­сор берет на себя. Но немало забот выпада­ет и на долю прог­раммис­та. Так, перед любыми опе­раци­ями при­ходит­ся заботить­ся о при­веде­нии типов и, что еще хуже, о про­вер­ке при­над­лежнос­ти опе­ран­дов к заранее ого­ворен­ным гра­ницам. Нап­ример, если мы сло­жим бай­ты +127 и +1, то получим –128 (!). Да, вот такая любопыт­ная матема­тика! Источник ошиб­ки в том, что получив­ший­ся резуль­тат «заехал» в зна­ковый бит, от чего положи­тель­ное 128 ста­ло трак­товать­ся как отри­цатель­ное 128. Подоб­ных оши­бок избе­жать очень и очень труд­но. А мно­гочис­ленные про­вер­ки, раз­бро­сан­ные по телу прог­раммы, отри­цатель­но ска­зыва­ются на ком­пак­тнос­ти и про­изво­дитель­нос­ти кода. Всех этих проб­лем нет в тро­ичной логике. Трит может при­нимать зна­чения –1, 0, +1, дос­таточ­ные для пред­став­ления как положи­тель­ных, так и отри­цатель­ных чисел, безо вся­ких допол­нитель­ных ухищ­рений.

А тро­ичная логика? Она поз­воля­ет решить любую задачу зна­читель­но мень­шим чис­лом опе­раций. Выше мы уже рас­смат­ривали при­мер срав­нения двух чисел, поэто­му не будем пов­торять­ся. Покажем лишь откры­вающуюся воз­можность неп­ротиво­речи­вой обра­бот­ки оши­бок.

Рас­смот­рим прос­той при­мер: прог­рамма зап­росила у опе­раци­онной сис­темы нем­ного памяти для собс­твен­ных нужд, для чего выз­вала соот­ветс­тву­ющую сис­темную фун­кцию. Опе­раци­онная сис­тема пок­ряхте­ла дис­ком и вер­нула ука­затель на выделен­ный реги­он, который прог­рамма с радостью при­нялась исполь­зовать. Но ведь память‑то не бес­конеч­на, и рано или поз­дно нас­тупит момент, ког­да ее не хва­тит, и фун­кция вер­нет в качес­тве ука­зате­ля ноль — то есть попыта­ется сиг­нализи­ровать об ошиб­ке. Вот имен­но, попыта­ется! Если прог­раммист забудет про­верить получен­ное зна­чение, то Windows не оста­нет­ся ничего ино­го, как зах­лопнуть некор­рек­тно работа­ющее при­ложе­ние. Пом­нишь про слу­чай с про­хожим и погодой? Так и у вся­кой фун­кции спер­ва при­ходит­ся спра­шивать «ты получи­ла дос­товер­ный резуль­тат?» и если да, то «сооб­щи же его». Если прог­раммист забудет это сде­лать (или сде­лает неп­равиль­но), то воз­ника­ет неш­татная ситу­ация, ког­да фун­кция не может подоб­рать слов, что­бы ска­зать: «Да не знаю я резуль­тата, оши­боч­ка выш­ла!»

Сетунь

В 1957–1958 годах в сте­нах уни­вер­ситета МГУ была пос­тро­ена прак­тичес­ки единс­твен­ная на сегод­няшний день серий­ная тро­ичная вычис­литель­ная машина. Это был ком­пак­тный прос­той про­тотип нынеш­него пер­сональ­ного компь­юте­ра, и он затем успешно тру­дил­ся на мно­гих пред­при­ятиях нашей необъ­ятной стра­ны от Ашха­бада до Якут­ска. Выбор архи­тек­туры был про­дик­тован в пер­вую оче­редь тре­бова­ниями к сто­имос­ти и надеж­ности ЭВМ, поэто­му инже­неры оста­нови­лись на быс­тро­дей­ству­ющих порого­вых маг­нитных уси­лите­лях. Их трой­ствен­ная при­рода поз­воляла дос­тичь той же про­изво­дитель­нос­ти мень­шим (по срав­нению с дво­ичной логикой) чис­лом эле­мен­тов.

На­деж­ность экспе­римен­таль­ного образца ока­залась выше вся­ких пох­вал. С неболь­шими ремон­тами (пот­ребовав­шимися из‑за завод­ских дефек­тов двух диодов и одно­го тран­сфор­матора) эта машина про­рабо­тала свы­ше 15 лет, находясь в неп­рерыв­ной экс­плу­ата­ции в усло­виях рез­ких перепа­дов тем­ператур и пита­юще­го нап­ряжения.

Вы­чис­литель­ная мощ­ность «Сетуни» была пре­вос­ходной для машин того вре­мени. Опе­ратив­ная память, сос­тоящая из 162 девятит­ритных яче­ек, исполь­зовалась как кеш мед­ленной внеш­ней «барабан­ной» памяти. Учи­тывая, что код машин­ной опе­рации уме­щал­ся все­го в трех три­тах (что поз­воляло кодиро­вать до 33 = 27 команд), даже такого малень­кого окна с лих­вой хва­тало для раз­мещения боль­шинс­тва под­прог­рамм и обра­баты­ваемых ими дан­ных, обра­щение к мед­ленной внеш­ней памяти сво­дилось к миниму­му.

Са­мое при­ятное зак­лючалась в том, что коман­ды трех­знач­ной логики поз­воляли решать задачи мень­шим чис­лом опе­раций в срав­нении со сво­ими дво­ичны­ми соб­рать­ями. Оче­вид­но, это вылива­лось в эко­номию ресур­сов, как опе­ратив­ной памяти, так и про­цес­сорной мощ­ности. В 1970 году была выпуще­на зна­читель­но усо­вер­шенс­тво­ван­ная модель «Сетунь-70», с муль­тис­тековой под­дер­жкой, обес­печива­ющей наилуч­шую про­изво­дитель­ность для вычис­лений с магазин­ной переда­чей про­межу­точ­ных резуль­татов (неч­то похожее было в пер­вых совет­ских мик­рокаль­кулято­рах, нап­ример в Б3-19М).

Но, увы, широкой популяр­ности «Сетунь-70» так и не снис­кала, да и сама три­логи­ка, нес­мотря на оче­вид­ные пре­иму­щес­тва, была на дол­гие годы забыта, оста­ваясь лишь в теоре­тичес­ких раз­работ­ках, ни одна из которых так и не была воп­лощена в закон­ченную модель…

История трилогики

Три­логи­ка была сфор­мулиро­вана Лукасе­вичем в 1920 году. В ней фигури­рова­ли тер­мы «исти­на», «ложь» и «воз­можно». В качес­тве основных фун­кций рас­смат­ривались отри­цание и импли­кация. Про­изводны­ми от них счи­тались конъ­юнкция и дизъ­юнкция. Спус­тя один год на свет появи­лась обоб­щенная n-рич­ная сис­тема Пос­та, которая опе­риро­вала дву­мя видами отри­цания: цик­личес­кого и сим­метрич­ного.

N1([N1= [x] + 1 при [x] < n и [N1n] = 1) x]

N2 ( [N2x] = n – [x] + 1)

В булевой логике (n = 2) эти отри­цания сов­пада­ют, но уже в три­логи­ке (n = 3) по‑раз­ному опе­риру­ют с эти­ми логичес­кими опе­раци­ями.

В 1938 году была опуб­ликова­на так называ­емая логика Боч­вара, манипу­лиру­ющая выс­казыва­ниями двух типов — име­ющи­ми смысл (истинные или лож­ные) и бес­смыс­ленны­ми. В ней под­держи­валось три вида отри­цаний: ¬a — внеш­нее отри­цание, ~a — внут­реннее отри­цание и ã — внут­реннее отри­цание внеш­него утвер­жде­ния.

Нем­ногим поз­же, в 1946 году, необ­ходимость опи­сания про­цес­сов кван­товой механи­ки вынуди­ла Рей­хен­баха соз­дать свою модель три­логи­ки. Он ввел три вида отри­цаний: цик­личес­кое, диамет­раль­ное и пол­ное, раз­лича­ющиеся в основном их дей­стви­ем в отно­шении «неоп­ределен­ности».

На заре раз­вития вычис­литель­ной тех­ники «сер­дцем» любой ЭВМ было реле — устрой­ство, конс­трук­тивно сос­тоящее из пары кон­тактов, яко­ря и обмотки. Час­то учеб­ники информа­тики при­водят реле в качес­тве «клас­сичес­кого» дво­ично­го эле­мен­та. На самом же деле сущес­тво­вали и поль­зовались боль­шой популяр­ностью так называ­емые поляри­зован­ные реле, замыка­ющие раз­личные кон­такты в зависи­мос­ти от поляр­ности сиг­нала. Конс­трук­тивно они отли­чались лишь допол­нитель­ной груп­пой кон­тактов и механиз­мом балан­сиров­ки яко­ря для удер­жания его в ней­траль­ном положе­нии.

Ана­логич­но в сов­ремен­ных компь­юте­рах широко исполь­зует­ся так называ­емая динами­чес­кая память, сос­тоящая из мно­жес­тва кон­денса­торов, заряжен­ное сос­тояние которых трак­тует­ся логичес­кой еди­ницей, нап­ротив, раз­ряжен­ное — логичес­ким нулем. На самом же деле каж­дая ячей­ка опе­ратив­ной памяти компь­юте­ра — это тро­ичный эле­мент, спо­соб­ный находить­ся в трех сос­тояниях: –1 (отри­цатель­ный заряд), 0 (нет заряда), +1 (положи­тель­ный заряд). Эле­мен­тарная база боль­шинс­тва компь­юте­ров тро­ична по сво­ей физичес­кой при­роде.

Трех­ста­биль­ный триг­гер тран­зистор­ной логики гораз­до слож­нее сво­его двух­ста­биль­ного соб­рата. Это и ста­ло при­чиной домини­рова­ния дво­ичной логики на ран­них эта­пах раз­вития крем­ниевой цивили­зации. Тран­зистор — дво­ичное устрой­ство, обла­дающее дву­мя сос­тояниями. «Открыт», если на базу пода­ется положи­тель­ный сиг­нал, и «Зак­рыт» в осталь­ных слу­чаях (речь идет толь­ко об эле­мен­тах p-n-p, пос­коль­ку про­изводс­тво тран­зисто­ров n-p-n соп­ряжено со зна­читель­ными тех­нологи­чес­кими труд­ностя­ми).

Для эму­ляции треть­его сос­тояния приш­лось бы при­бегать к слож­ным конс­трук­циям, вклю­чающим в себя более одно­го тран­зисто­ра, что понача­лу соч­ли нераци­ональ­ным. Сегод­ня же повышать про­изво­дитель­ность компь­юте­ров уве­личе­нием так­товой час­тоты ста­новит­ся труд­нее, чем наращи­вать конс­трук­тивную слож­ность чипа.

ЗАКЛЮЧЕНИЕ

Мож­но ожи­дать, что прог­раммы, написан­ные с исполь­зовани­ем тро­ичной логики, будут содер­жать на порядок мень­ше оши­бок и сок­ратят сро­ки и зат­раты на пред­варитель­ное тес­тирова­ние. Но если все так хорошо, то почему же до сих пор не реали­зова­но? Почему нам при­ходит­ся воевать с глю­ками, изыс­кивать день­ги на нек­ста­ти подоро­жав­шую опе­ратив­ную память, ког­да яко­бы такие прос­тые тех­ничес­кие при­емы поз­воля­ют это­го избе­жать? Увы, тро­ичная логика озна­чает пол­ную несов­мести­мость с нашим мрач­ным битово‑бай­тным прош­лым. При­дет­ся не толь­ко переком­пилиро­вать все сущес­тву­ющие наработ­ки, но и соз­давать новые язы­ки. Ведь си, пас­каль, бей­сик — все они проч­но «при­вяза­ны» к дво­ичной логике. Как минимум еще одной очень серь­езной проб­лемой явля­ется отсутс­твие полуп­ровод­никовых эле­мен­тов с тре­мя ста­биль­ными сос­тояниями и име­ющих соиз­меримую слож­ность с исполь­зуемы­ми сегод­ня бинар­ными логичес­кими вен­тилями.

Впро­чем, новый про­цес­сор может эму­лиро­вать ста­рый, выиг­рывая в про­изво­дитель­нос­ти по при­чинам, ука­зан­ным в начале статьи. В основном — бла­года­ря уско­рен­ному дос­тупу к памяти, за счет ее ком­пак­тно­го пред­став­ления. Разуме­ется, и ядро, работа­ющее на три­логи­ке, в какой‑то сте­пени уве­личит про­изво­дитель­ность. Но оста­ется откры­тым воп­рос: появит­ся ли под­дер­жка три­логи­ки для новых прог­рамм? Или же это будет глу­боко скры­то внут­ри про­цес­сора?