Як українець переписав алгоритм Google Search, отримав офер у Facebook та просуває Україну в США
Архітектор Ігор Марков родом з Києва. 1993 року він переїхав до США, щоб пройти аспірантуру Каліфорнійського університету в Лос-Анджелесі. Коли Марков випустив своє перше академічне ПЗ в опенсорс, його одразу почали використовувати IBM, Intel і Cadence. Науковець отримував офери Google, Meta та Nvidiа, а також викладав алгоритми у Мічиганському університеті та Стенфорді.
Окрім того, він є директором фонду Nova Ukraine, яка фінансово допомагає Україні та лобіює її інтереси в США.
DOU поспілкувався з Ігорем Марковим про його захоплення мікроелектронікою та квантовими комп’ютерами, досвід переписування алгоритму Google Search, оптимізацію PyTorch на GPU у Meta та майбутнє інженерів в епоху ШІ.
Завантаження 32 тонн медикаментів для України від Nova Ukraine, березень
«Моє ПЗ для мікросхем використовували IBM, Intel, Cadence»
Одне з моїх наукових захоплень — проєктування мікросхем. В аспірантурі Каліфорнійського університету в Лос-Анджелесі (UCLA) я створив ПЗ, покликане зробити дроти на мікросхемах трохи коротшими. Розташування координат на мікросхемі дуже важливе, тому що маленькі пристрої, які поєднані дротами, мають бути розміщені близько один до одного. Умовно, за рандомних позицій таких компонентів потрібна величезна кількість дроту. Якщо ж оптимізувати розташування, то відстані між ними будуть невеликі.
При цьому впродовж багатьох років працював закон Мура, за яким кількість транзисторів на мікросхемі подвоюється кожні 18 місяців, а вартість виробництва транзистора зменшується. Тобто на одному й тому самому чипі можна було розмістити більше компонентів.
І проблема найбільшої затримки в проєктуванні мікросхем, — тобто часу, який мікросхема потребує на виконання якоїсь операції, — полягала в дротах.
Змінюючи довжину дротів через алгоритми, мені вдалося зробити мікросхеми ефективнішими в середньому на 10%. Це була безпечна оптимізація, яка нічого не ламає та покращує фізичну реалізацію мікросхеми. За кілька років це стало впливати й на витрати енергії, тому що дроти потребували багато енергії на перемикання сигналів тощо.
Підхід, який я використав у дисертації, базувався на розділі графів. Тобто мікросхема моделюється графом, з вершинами й ребрами, і сегментується щоразу на дві частини. Потім ці частини розділяються рекурсивно. Зрештою з’єднання між частинами стають мінімальними, і за одним з моїх алгоритмів дроти стали сполучати переважно тільки ті частинки, які були розташовані близько одна до одної.
«Я взяв state of the art алгоритмічного й математичного підходів»
Згодом я випустив це програмне забезпечення в open source. Його завантажили майже всі відомі американські йне тільки компанії, які займалися мікросхемами. Зокрема, IBM, Intel, Cadence тощо. Деякі компанії потім використовували ПЗ комерційно. Якось після доповіді на конференції до мене підійшов підприємець і запропонував разом запустити стартап з використанням моєї розробки. Коли я не погодився, мені ще чотири рази підвищували оплату на 20%. Пропозиція була приємна, та я відмовив.
Річ у тім, що я хотів займатися наукою, навколо витало багато ідей для цієї галузі. Є такий вислів — fame or fortune, тобто будеш або відомим, або багатим. Так склалося, що я став відомим [усміхається]. Попри те, що коштів за це я не одержав, IBM, Synplicity та Texas Instruments підтримали дослідження моєї університетської лабораторії науковими грантами.
Зрештою, мій науковий керівник і я не задумувалися, чи будуть компанії використовувати це рішення, коли виклали його в опенсорс. Ми прагнули просунути академічну науку, щоб ті, хто працював над схожими темами в університеті, могли порівняти свої напрацювання з моїм забезпеченням.
Головний офіс Google, 2016
800 студентів відвідувало курс програмування в Мічигані
Після захисту дисертації у 2000 році я залишився працювати в Мічиганському університеті в Енн-Арборі. Окрім мікросхем, мене драйвили квантові комп’ютери, однак на той час їх дослідження залишалися дуже теоретичними. Більшість фахівців були фізиками й спеціалістами з теоретичної кібернетики. І вони радше досліджували, що можна обчислювати на квантовому комп’ютері, а що не можна.
Проте я бачив очевидні аналогії з мікросхемами, особливо щодо оптимізації обчислень за часом. Ті статті, які я опублікував на цю тему 20 років тому, все ще популярні, а результати досліджень досі використовують компанії у своїх продуктах.
Я почав викладати на посаді асистента
Пригадую, як з одним студентом ми опублікували 10 статей за декілька років (одна з них навіть здобула премію як найкраща стаття року). Він вступив на аспірантуру до всіх топових американських вишів, з-поміж яких обрав Принстон, потім улаштувався професором у Берклі. Одна з моїх колишніх аспіранток працювала в IBM Research, тепер викладає в Єльському університеті.
«Коли захистився мій12-й аспірант, я відчув, що хочу застосувати свої знання в індустрії»
Зробити щось таке, чого ще не пробував. І якраз тоді мене запросили в Google. Це був, як то кажуть, cold call: зателефонував рекрутер і покликав у Каліфорнію на інтерв’ю. Було кумедно, що більшість питань стосувалася програмування та алгоритмів — саме того, що я багато років викладав в університеті. Причому свого часу я перепланував весь курс, зробив його практичнішим. У Мічиганському університеті й досі використовують мої матеріали. Кілька років по тому я разом з двома колегами знову викладав цей курс — його слухало 800 студентів упродовж семестру.
Отож під час інтерв’ю в Google я не лише знав, як розв’язати задачі, а й що запитати додатково. Натоді в компанії практикували bar raiser interviews: упродовж дня з кандидатом проводили п’ять-шість інтерв’ю, після успішного проходження яких потрібно було виконати нестандартне завдання від фахівця з олімпіадним досвідом. Я впорався, навіть запропонував трохи складніший варіант з рішенням.
Переписав важливу частину алгоритму Google Search
Коли мене запросили в команду, то дали змогу обрати групу. Я хотів працювати над чимось фундаментальним. А оскільки Google Search використовують мільярди людей, то покращення пошуку видалося дуже актуальним.
У Google Search була стадія перевірки на тривіальність запиту. У пошукових запитах можна поєднувати різні терміни логічними зв’язками. Наприклад, шукати статті зі словами «Київ» чи «Одеса» або «Київ чи не Київ». Якщо подумати логічно, то під поняття «Київ чи не Київ» підпадає все що завгодно. І цей крок перевірки на тривіальність іноді майже зациклювався. Він міг тривати секунди, а це дуже довго. Обробка пошукових запитів має займати максимум п’яту частку секунди — типовий час реакції людини.
У програмуванні алгоритм повинен працювати за якийсь час, а якщо його неправильно запрограмувати, все відбуватиметься значно довше. Є такі вирази — O(n) і O(n2), де n — оцінка розміру вхідних даних. Наприклад, один алгоритм може швидко обробляти дані за два чи три проходи, а інший може повертатися більше разів, якщо даних багато.
Я поцікавився думкою колег, у чому ж причина такої проблеми. За їхніми припущеннями, алгоритм, який має працювати за O(n), запрограмували так, що він потребує довше часу — O(n2). Моє завдання було розібратися в цьому й зробити пошук швидшим.
Занурившись, я помітив проміжні результати, які не тільки потребували куди більше часу, ніж n2, а іноді сягали розміру 2n. Я переписав весь алгоритм. Тобто замість того, щоб краще його запрограмувати, я зовсім прибрав проміжні результати й покращив час роботи з O(2n) до O(n).
Це було майже фантастичне вдосконалення. Проміжний пошук багато років працював на всіх запитах у Google, але з’явилися проблеми, коли n збільшилося.
Android garden, Google, 2014
Про те, що найбільше запам’яталося в Google, і систему, яка знаходила найкращі 10 сторінок пошуку
Пригадую, компанія розсилала листівки про синдром самозванця — почуття, коли думаєш, що ти не на своєму місці й не заслуговуєш тут бути. Задум з листівками був дуже слушний. На той час у Google працювало багато вчорашніх випускників, які хвилювалися, що не зможуть працювати на очікуваному рівні, потребували підтримки.
Система Google — одна з найскладніших у світі. Тому що це і апаратне, і програмне забезпечення, алгоритми, комп’ютерні мережі, обробка natural language. Я сам був щиро вражений, наскільки в компанії все оптимізовано й швидко працювало.
На час роботи в Google я взяв дворічну відпустку в університеті, а тоді повернувся на один семестр і попросив про сабатікал. У якийсь момент побачив можливість утілити в компанії те, що там вважали неможливим.
Звичайний пошук Google оптимізований для вебсторінок, де можна обчислити PageRank — індекс авторитетності сторінки відповідно до посилань на неї. Але коли потрібно знайти документи за іншими критеріями, які вказав користувач, усе набагато складніше. З початку
Я розробив систему, яка знаходила
IPO компанії lonQ, яку консультував Ігор. Нью-Йоркська фондова біржа, 2021
Оптимізувати PyTorch на GPU у Meta
Коли я пішов з Google 2017 року, у мене був офер від Facebook. Раніше, коли я тільки-но влаштовувався в Google, я порівнював зарплату із викладацькою. У Facebook же мені запропонували вищу зарплату й утричі більше акцій.
У компанії дуже хотіли, щоб я зайнявся пошуком, який був у них не зовсім якісним. Але я планував спробувати щось зовсім інше й пішов боротися з фейк-ньюз — у News Feed Integrity. Я працював у групі, яка вивчала поляризацію суспільства. Але через вибори в Штатах і політичні зміни Цукерберг у якийсь момент вирішив закрити цей відділ.
«У Meta я перейшов розробляти інфраструктуру для систем штучного інтелекту»
Одна така система опрацьовувала 4 мільйони запитів на секунду і мала більш як сотню клієнтів у компанії. Вона вирішувала різноманітні завдання «легкої ваги». Наприклад, передбачити, як довго сервер працюватиме над запитом, вирішити, чи варто зберігати файли на мобільному Facebook-застосунку довше або як краще відреагувати, коли юзер забув пароль. Система слугувала для внутрішнього користування, але на неї покладалося понад сотню продуктових команд. Вона приваблювала тим, що давала змогу використовувати штучний інтелект без написання коду, який потребує знання з ШІ.
Після того як я підготував доповідь про нашу роботу на конференції KDD 2022 у Вашингтоні, я став працювати у групі, яка оптимізовувала PyTorch на GPU, тобто на графічні карти. PyTorch — це система програмування та компілятор, який використовують для Deep Learning усі, окрім Google. У Google є своя — старіша й менш ефективна — система TensorFlow. PyTorch реально переміг ці змагання, особливо в простішому використанні.
Але код, який Nvidia писала прямо для GPUs для тренування та інференції Deep Nerual Networks, був набагато ефективнішим. Тож челендж був на поверхні: покращити компілятор, щоб швидке програмування мовою високого рівня не відставало від коду, ретельно оптимізованого для GPU.
Виявилося, що великою мірою челендж стосувався руху даних до GPU, всередині GPU та з GPU. Для сучасних мереж DNN, які занадто великі для одного GPU, важливо розділити їх на частини, щоб використати десятки GPU, особливо для тренування LNN. Nvidia та AMD випускали нові GPU кожні два роки, і ціль досить швидко рухалася. Тому я організував семінар, на якому ми розбирали оптимізації для тренування LLM i вирішували, що варто втілювати в PyTorch.
На той час я вже працював п’ять з половиною років у команді Meta і зрозумів, що в бігтех, на жаль, навіть на просунутих рівнях кожен працює над вузькою спеціалізацією. Багато кому це подобається, але рано чи пізно може завадити перемкнутися на перспективні проєкти. Наприклад, пошук у Google був перспективним 2014 року, але вже не таким привабливим
Synopsys, Nvidia та викладання
Перед тим як звільнитися з Facebook 2023 року, я пробувався в Nvidia та Synopsys — й отримав офери в обох компаніях. У Nvidia пропонували суттєво більший пакет компенсації, але з вузькою спеціалізацією суто на квантових комп’ютерах. Водночас у Synopsys обіцяли цікавіші завдання, тож я прийняв їхній офер Мій головний фокус у компанії — штучний інтелект для проєктування мікросхем, а також проєктування квантових комп’ютерів, різноманітні алгоритми.
З 2018 року я віддав свою позицію в Мічиганському університеті.
«Дуже тішуся, що мені не довелося викладати за часів ChatGPT»
Через нього студенти не роблять домашки самостійно й потім не засвоюють матеріал, не практикуються розв’язувати задачі, і це велика проблема.
Мої екзаменаційні завдання завжди були складними. Нині можна сформулювати їх так, щоб ChatGPT видавав неправильні рішення, хоч це непросто. Бо коли студенти отримують готові відповіді, то мало чого навчаються. Це потребує повністю іншої структури навчання.
Сьогодні в Америці постала інша проблема: уряд почав скорочувати фінансування наукових досліджень, що може серйозно підкосити університетську науку.
Із СТО Qolab Джоном Мартінісом (зліва) на Synopsys Executive Forum, 19 березня 2025 року
«2033 рік обіцяє бути особливо цікавим». Про роботу в галузі квантових обчислень
Більша частина моєї академічної діяльності була пов’язана з мікроелектронікою, я написав кілька книжок і маю широке розуміння проєктування мікросхем. Кілька років тому ця галузь отримала новий поштовх завдяки використанню штучного інтелекту. Але знання фундаментальних основ не менш важливе.
Я працював у Synopsys у 2008 році під час університетської відпустки, тому мене запросили керувати проєктами зі штучного інтелекту в проєктуванні чипів. Це набагато цікавіше, ніж виконувати вузьке завдання у Meta, особливо враховуючи, що робочий клімат у Meta почав погіршуватися кілька років тому. Зараз я співпрацюю з кількома групами в Synopsys, відвідую конференції та знову спілкуюся зі своїми старими друзями по професії.
Протягом багатьох років у Synopsys існувала група ентузіастів квантових обчислень, однак цей напрям вважали надто далеким. Уявіть моє здивування, коли у 2025 році керівництво зацікавилося квантовими обчисленнями й попросило мене представляти Synopsys на виконавчому форумі в березні.
Традиційно Synopsys допомагає іншим компаніям проєктувати мікросхеми, використовуючи економіку програмного забезпечення (розробляти один раз, продавати багато разів). Ми дотримуємося тієї самої стратегії й у квантових обчисленнях — допомагаємо іншим компаніям створювати кубіти, починаючи з чисельного моделювання на атомному рівні та мікрохвильових схем. Разом із Hewlett Packard, Nvidia, Applied Materials та іншими компаніями ми беремо участь у великому проєкті під керівництвом DARPA зі створення квантових комп’ютерів і оцінки їхнього економічного впливу до 2033 року. Наші щотижневі зустрічі нагадують наукову фантастику — ми обговорюємо кубіти, що працюють поблизу абсолютного нуля, магічні стани й телепортацію. Згідно з нашими планами, 2033 рік обіцяє бути особливо цікавим.
Повстання машин і дрони
Довгострокові дискусії про спроможності ШІ — це дуже близько до політики. Повстання машин не буде серйозною проблемою і я не рекомендую молодим людям займатися науковою політикою, don’t waste your time.
Згадаймо, що сталося в OpenAI. Розбираючись, чи треба боятися штучного інтелекту настільки, щоб сповільнити розробку системи ШІ, люди втратили роботу. Але найсильніші науковці та підприємці заснували власні компанії. Відомо, що в OpenAI була група, яка намагалася зробити штучний інтелект безпечним. Очолював її професор з MIT. І цю групу прикрили, тому що керівництво не погоджувалося з фахівцями щодо коштовних ресурсів для такої роботи.
Є схожа компанія — Anthropic, яку заснували колишні фахівці OpenAI. І вона відрізняється від OpenAI саме своєю політикою щодо безпеки ШІ. Anthropic намагається нас переконати, що потрібно боятися штучного інтелекту, тому що за кілька років він залишить усіх без роботи й підкорить світ. І тільки Anthropic допоможе захиститися [усміхається].
Майже 10 років тому мене попросили зробити доповідь про апокаліпсис, спричинений ШІ. Це жанр наукової фантастики, але в більшості сценаріїв, щоб штучний інтелект заволодів світом, йому потрібно заволодіти фізичними ресурсами. І це складно, тому що люди можуть просто не дозволити вмикати-вимикати енергію, не віддати під контроль потужні електростанції та мережі. Без фізичного доступу навіть живим гуманоїдам нереально заволодіти сусідською енергосистемою, як це добре відомо в Україні.
Чому ми боїмося штучного інтелекту? З огляду на історію, людям просто треба чогось або когось боятися. Хижаки, вампіри, монстри під ліжком — у доповіді я назбирав цілу колекцію. Насправді це еволюційна фіча: тих, хто не боявся, з’їли або перемогли.
Водночас деякі речі передбачення щодо ШІ безсумнівно мають сенс. Полювання дронів на людей, яке показували у фільмах про Термінатора, тепер майже реальність. Або натовпи автономних агентів з «Матриці». Але є такий термін end-to-end, тобто замкнутий цикл, — ШІ на це ще й близько не спроможний. Anthropic нещодавно спробував залучити свою LLM до керування кіоском з їжею та напоями. Та результат не виправдав надій.
«LLM гостро не вистачало здорового глузду»
Якщо говорити про серйозніші питання, як-от виробництво дронів та їхнє постійне покращення, то тут досі не обходиться без складнощів. Використовувати БПЛА набагато простіше, ніж проєктувати їх і масово виготовляти.
Дрони адаптують до фронту, до розробок, які має супротивник. Це еволюція, яка під силу людині, компанії чи державі. . Однак для штучного інтелекту повний цикл — нездійсненне завдання ні зараз, ні в найближчому майбутньому. Завжди будуть проблеми, що потребують обдумування, поєднання різноманітних знань, творчого підходу й рішень, які не можна скопіювати з минулого досвіду.
Щодня ШІ нарощуватиме можливості, і дуже важливо не відставати від ключових технологій. Інженерам точно варто його опановувати. Спеціалісти, які використовуватимуть ШІ, зможуть робити значно більше.
Попит на інженерів стрімко зростає. Наприклад, прогнозують, що 2030 року в Америці не вистачатиме
До того ж писати програмне забезпечення для GPU досить важко, тому ще не скоро штучний інтелект зможе повністю замінити досвічених інженерів. Утім, він візьме на себе рутинну роботу.
Відмовився допомагати росіянам удосконалювати програму з мікроелектроніки
Я не дуже перетинаюся з українськими науковцями чи інженерами. Моя робота з квантовими комп’ютерами 20 років тому мало кого цікавила. За останнє десятиліття ця галузь пішла вгору. У Київському політехнічному інституті є інтерес до оптимізації мікросхем, але поки що на мене ніхто не виходив.
До речі, перед Революцією гідності я бував у москві, 2013 року викладав стислий спецкурс для аспірантів і студентів у московському державному університеті. Навіть приймав екзамени. Під час спілкування з російськими науковцями спершу мені здавалося, що вони намагаються розвивати consumer electronics, тобто побутову електроніку. Але досить швидко я зрозумів: головні для них галузі — це космос і військові застосування. Вирішив, що не хочу допомагати росіянам готувати спеціалістів з електроніки. А з
Ігор Марков з Віктором Ющенком та Ніком Білогорським
Про адвокацію України в США
Починаючи з 2013 року, я був активним користувачем соцмережі Quora. Там люди ставили запитання про комп’ютери, математику, університети, історію, географію, політику — на будь-які теми — і мої відповіді були популярними. П’ять років поспіль я отримував відзнаку Top Quora writer і досі маю 80 000 підписників, хоча профіль вже неактивний.
З 2014 року багато запитань стосувалися України, і це привернуло велику увагу. Саме в цей час я переїхав із Мічигану до Каліфорнії працювати на Google, але там майже нікого не знав. Тоді я прийшов на мітинг Nova Ukraine — і деякі люди впізнали мене завдяки Quora.
Завдяки моєму академічному досвіду мене запросили до Консультативної ради Nova Ukraine, яка тоді була маленькою організацією. Вона переважно організовувала вуличні акції, популяризувала українську культуру й відправляла допомогу Україні контейнерами.
Через кілька років мене обрали до правління. У США я представляю Nova Ukraine у правлінні American Coalition for Ukraine (ACU), де обіймаю посаду заступника голови.
Під час COVID-19 ми закуповували засоби індивідуального захисту і кисневі концентратори для України. З початку лютого
Медичні проєкти завжди були головними, починаючи з чартерного рейсу, що доставив 32 тонни допомоги із Сієтла до Любліна для передачі Міністерству охорони здоров’я. Згодом ми почали контактувати з обраними посадовцями. Що шість місяців ми літаємо до Вашингтона на саміт Ukraine Action Summit, де відстоюємо важливі законопроєкти та резолюції.
У 2024 році адвокація стала ще важливішою — ми інформуємо посадовців про події в Україні й пояснюємо, що станеться у світі, якщо Україна впаде. Ми почали розміщувати рекламні щити по всій території США, щоб привернути увагу до викрадених росією дітей.
В Україні у нас офіс у Києві та представництва в багатьох інших містах — понад 60 членів Nova Ukraine займаються різноманітними проєктами, фінансують волонтерів і партнерів. Загалом ми витратили понад $130 мільйонів в Україні.
