Przewiduj czasy działania gęstej algebry liniowej

9

Chciałbym przewidzieć środowiska wykonawcze dla gęstych operacji algebry liniowej na określonej architekturze przy użyciu określonej biblioteki. Chciałbym nauczyć się modelu zbliżonego do funkcji

$F_{op} \;::\;$ rozmiary wejściowe czas pracy w $\rightarrow$

do operacji takich jak mnożenie macierzy, dodawanie elementów, rozwiązywanie trójkątne itp.

Podejrzewam, że te środowiska wykonawcze są w większości przewidywalne ze względu na regularność operacji, gdy przekroczysz rozmiary problemów, które wygodnie mieszczą się w pamięci podręcznej.

Pytania:

Czy to założenie jest realistyczne? Czy funkcja czasu wykonywania może być prawie deterministyczna?
Czy mogę założyć, że ta funkcja będzie wielomianowa pod względem wielkości wejść? (tzn. spodziewam się, że mnożenie gęstej macierzy będzie wyglądało jak dla i jakiś współczynnik skalarny) $\alpha n\times k\times m$ $A_{nk}\times B_{km}$ $\alpha$
Czy jest już gdzieś nad tym praca?
Mój obecny plan polega na regresji metodą najmniejszych kwadratów za pomocą . Jakieś inne sugestie? $L_1$

Edycja: Aby być jasnym, szukam środowisk uruchomieniowych, a nie FLOP ani innych typowych wskaźników wydajności. Chcę ograniczyć się do jednej konkretnej architektury.

linear-algebra machine-learning

— MRocklin
źródło

10

Ostatnio pracowałem nad tym właśnie tematem. Możesz rzucić okiem na nasz artykuł: http://arxiv.org/abs/1209.2364 .

Dlaczego interesuje Cię przewidywanie w czasie wykonywania procedur algebry liniowej? Czy zamierzasz używać modelu do określonego celu?

— Elmar Peise
źródło

Dzięki za link. Spojrzę na to. Interesuje mnie to, ponieważ podejrzewam, że z tego samego powodu jesteś. Zautomatyzowany wybór algorytmu i szeregowanie wyrażeń macierzowych. W tej bardzo regularnej i przewidywalnej dziedzinie powinno być możliwe wiele innych niemożliwych problemów.

— MRocklin

6

Istnieje wiele wcześniejszych prac. Większość twórców bibliotek algebry liniowej publikuje wyniki wydajności w kategoriach wydajności zmiennoprzecinkowej, które można przeliczyć na czasy wykonywania.

Na przykład Google dla „wydajności DGEMM” daje następujące wyniki: http://math-atlas.sourceforge.net/timing/3_5_10/index.html .

Zasadniczo można oczekiwać, że odpowiedzi nie będą płynne. W pobliżu pewnych rozmiarów problemów (które dotyczą rozmiarów pamięci podręcznej) będą występowały skoki lub skoki. Powinieneś także spodziewać się płaskich stawek, a zatem i regionów liniowych dla szerokiego zakresu rozmiarów problemów. Nie oczekuję, że dopasowania wielomianowe będą bardzo pomocne.

Biorąc pod uwagę szeroko zakrojone wysiłki w zakresie analizy porównawczej, łatwiejsze może być zestawienie wyników i interpolowanie w razie potrzeby. Jaki jest Twój cel?

— Bill Barth
źródło

1

Plateau flop / s DGEMMwskazuje na

n^{3}

$n^3$ region, ponieważ to tempo, w którym klapy rosną wraz z rozmiarem problemu. Zgadzam się, że częściowe dopasowanie powinno być znacznie lepsze niż próba dopasowania pojedynczego wielomianu.

— Jed Brown,

Z mojego doświadczenia wynika, że konwersja flopów na środowiska wykonawcze jest trudna. W moim przypadku naprawdę obchodzą mnie tylko środowiska wykonawcze. Testuję wykonalność statycznego planowania.

— MRocklin

Z mojego doświadczenia wynika, że skoki / płaskowyże występują tylko w przypadku niewielkich rozmiarów problemów. Gdy wyjdziesz poza pamięć podręczną, wszystko jest dość płynne. Zgadzam się, że dodanie funkcji częściowych prawdopodobnie poprawiłoby dopasowanie.

— MRocklin