Symulowane wyżarzanie w asemblerze x86 (AMD64 + SSE)

Program, który powstał w sumie jako zakład z jednym z kolegów na kierunku. Celem było napisanie algorytmu symulowanego wyżarzania w asemblerze, bez łączenia z biblioteką C. Naturalnie, podjąłem ten zakład. Pierwszym problemem było opracowanie w jakiś sposób obliczania funkcji e^x, co w sumie sprawiło, że projekt utknął w miejscu na bardzo długi czas. Po bardzo dużej ilości googlowania i przeglądania zestawu instrukcji udało się jednak tego dokonać.

Nie było też do dyspozycji generatora liczb pseudolosowych, przez co byłem zmuszony do zastosowania bardzo prostego (i pewnie mało efektywnego pod względem prawdziwej losowości) algorytmu, którego kiedyś znalazłem na Wikipedii (teraz nie umiem go znaleźć).

Jedyną funkcją udostępnianą jest funkcja annealing() o następującym prototypie :
void annealing(float Tstart,float Tmin,float alpha,uint32_t *sol,int solsize,int(*crit)(uint32_t*,int));

Tstart, Tmin i alpha to parametry samego procesu wyżarzania (opisane w jednym z artykułów), *sol to wskaźnik na tablicę zawierającą solsize elementów 32-bitowych, które są początkowym rozwiązaniem algorytmu. Do oceny rozwiązania wykorzystywana jest funkcja przekazywana za pomocą wskaźnika *crit, przyjmująca wskaźnik na tablicę i jej rozmiar, oraz zwracająca liczbę całkowitą będącą oceną przekazanego do niej rozwiązania. Przed wywołaniem funkcji należy również wypełnić pola dwuelementowej tablicy seed, która jest używana jako ziarno dla generatora liczb pseudolosowych.

Kod funkcji został napisany zgodnie z ABI dla Linuksa AMD64 z rozszerzeniami SSE (jako że każdy procesor obsługujący operacje 64-bitowe ma też SSE). Po modyfikacjach na pewno będzie bezproblemowo działać na zwykłych i386.

Jako przykładowe zastosowanie tej funkcji napisałem krótki program w C, który znajduje rozwiązanie problemu TSP dla instancji gr17. Wątpię, żeby moja implementacja była w jakikolwiek sposób szybsza bądź lepsza od analogicznej w C – pewnie jest nawet gorsza. Program powstał po to, żeby pokazać, że można.

Źródełka tutaj. Do kompilacji wymagany NASM. Public domain.

Informacje o Daniel

freezingly cold soul
Ten wpis został opublikowany w kategorii komputer i oznaczony tagami , , , , . Dodaj zakładkę do bezpośredniego odnośnika.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s