Kompaktowy cyfrowy annealer Isinga z obliczeniami w pamięci i probabilistycznym bitem SRAM w technologii 28 nm dla problemu komiwojażera

Dlaczego lepsze trasy i układy scalone mają znaczenie

Codziennie ciężarówki dostawcze, samoloty i pakiety danych muszą wybrać trasę tak, aby wszystko dotarło na czas przy możliwie najniższym koszcie. Ten rodzaj zagadki, znany jako problem komiwojażera, szybko staje się przytłaczający nawet dla wydajnych komputerów wraz ze wzrostem liczby punktów do odwiedzenia. Artykuł będący podstawą tego streszczenia przedstawia nowy rodzaj wyspecjalizowanego układu, który radzi sobie z takimi zadaniami planowania tras znacznie wydajniej, wykorzystując pomysły zapożyczone z materiałów magnetycznych i wbudowując je bezpośrednio w standardową pamięć komputera.

Klasyczna zagadka: odwiedzić każdy punkt raz

Problem komiwojażera zadaje proste pytanie: mając listę miast i odległości między nimi, jaka jest najkrótsza trasa odwiedzająca każde miasto dokładnie raz i wracająca na start? Trudność polega na tym, że liczba możliwych tras eksploduje wraz z dodawaniem miast, więc sprawdzenie wszystkich opcji jest w praktyce niemożliwe. Zamiast tego współczesne podejścia poszukują bardzo dobrych, choć niekoniecznie idealnych, tras. Obiecująca metoda naśladuje sposób, w jaki sieć maleńkich „magnesików”, zwana modelem Isinga, może ustabilizować się w stanie niskiej energii reprezentującym dobre rozwiązanie. Poprzez kontrolowane pozwolenie tej sieci na „drgania” za pomocą losowych zmian, które stopniowo ustają, system unika złych lokalnych wyborów i znajduje lepsze trasy.

Przekształcenie układu pamięci w rozwiązywacz problemów

Zamiast wykonywać ten proces w zwykłych procesorach, autorzy wbudowali go bezpośrednio w sprzęt pamięci — strategię zwaną obliczeniami w pamięci. Zaprojektowali kompaktowy układ w technologii 28 nm, w którym każda maleńka komórka pamięci przechowuje zarówno informacje o odległościach, jak i uczestniczy bezpośrednio w obliczeniach. Sprytnie, układ wykorzystuje naturalne niedoskonałości produkcyjne komórek pamięci jako wbudowane źródło losowości, eliminując potrzebę dużych generatorów liczb losowych. Poprzez krótkie zaburzenie przechowywanych wartości kontrolowanym „pchnięciem” napięcia niektóre bity zmieniają stan probabilistycznie, dostarczając subtelnej losowości potrzebnej do procesu wyżarzania bez dodatkowych obwodów.

Dzieląc duże mapy na małe sąsiedztwa

Jedną z głównych przeszkód w zastosowaniu solverów w stylu Isinga do dużych zadań planowania tras jest ogromna ilość wymaganych danych: pełne odwzorowanie trasy dla 96 miast zwykle wymagałoby rozległej sieci połączeń i pamięci. Aby tego uniknąć, badacze grupują pobliskie miasta w małe klastry, a następnie układają te klastry w kilka poziomów hierarchii. Na najwyższym poziomie układ rozwiązuje kolejność klastrów; na kolejnym dopracowuje porządek miast w każdym klastrze; i tak dalej. Takie stopniowe podejście drastycznie zmniejsza ilość potrzebnej pamięci i połączeń, redukując złożoność sprzętową z rosnącej z czwartą potęgą liczby miast do rosnącej jedynie z kwadratem, a następnie dodatkowo kompresując przechowywane odległości przez gęste pakowanie jedynie naprawdę potrzebnych wartości.

Jak układ aktualizuje wiele wyborów naraz

Wewnątrz układu grupy trzech miast tworzą podstawowe bloki konstrukcyjne, które są przetwarzane równolegle. Macierz pamięci jest zorganizowana tak, że w obrębie każdego klastra obwód może szybko obliczyć zmianę całkowitej długości trasy w przypadku zamiany fragmentów trasy. Ponieważ niektóre klastry nie oddziałują bezpośrednio na siebie, system może zaktualizować wszystkie „nieparzyste” klastry w jednym kroku, a wszystkie „parzyste” w następnym, przyspieszając poszukiwanie, zachowując jednocześnie efekt wykonywania zmian pojedynczo. Podczas każdej rundy układ wykorzystuje swoje szumowe komórki pamięci, by z prawdopodobieństwem zdecydować, czy zaakceptować gorszy ruch — duże na początku, by eksplorować, i mniejsze później, by ustabilizować się — naśladując chłodzenie metalu i kierując trasę ku coraz krótszym długościom.

Z chipu laboratoryjnego do tras na dużą skalę

Prototypowy układ zawiera skromne 6 kilobitów tej specjalnej pamięci, a mimo to potrafi rozwiązać instancje problemu komiwojażera dla 96 miast w około 620 mikrosekund, zużywając mniej niż mikro-dżula energii. W porównaniu z wcześniejszymi układami zaprojektowanymi do tego samego zadania, osiąga poprawę nawet o setki razy w ilości pamięci wymaganej na jednostkę rozmiaru problemu. Symulacje pokazują także, że umieszczając wiele takich bloków pamięci obok siebie, ten sam projekt mógłby skalować się do problemów z tysiącami miast, utrzymując prawie liniowy wzrost sprzętu. Dla czytelnika niebędącego specjalistą kluczowa konkluzja jest taka, że przez przekształcenie znanej pamięci w aktywny rozwiązywacz problemów — i przez wykorzystanie nieuniknionych wad produkcyjnych jako użytecznej cechy — ta praca wskazuje drogę do małych, szybkich i energooszczędnych układów, które mogą w czasie rzeczywistym pomagać w planowaniu złożonych tras i grafików.

Cytowanie: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

Słowa kluczowe: problem komiwojażera, annealer Isinga, obliczenia w pamięci, sprzęt SRAM, optymalizacja kombinatoryczna