Czy są jakieś systemy kompilacji uwzględniające w harmonogramie względne oczekiwane czasy zadań?

Oto mała ilustracja mojego pytania:

Załóżmy zadanie kompilacji, które składa się z 4 niezależnych zadań o nazwie AD. D w sumie trwa dłużej niż AC.

System kompilacji, który nie może uwzględnić względnych czasów zadań, może zaplanować takie zadania:

---------------------------------------
CPU1: A  |    C   |
---------------------------------------
CPU2: B    | D                        |
---------------------------------------

W przeciwieństwie do tego, jeśli program planujący zdaje sobie sprawę z różnic czasu między zadaniami, może zaproponować znacznie krótszy harmonogram:

---------------------------------------
CPU1: A  |  B    |   C   |
---------------------------------------
CPU2: D                        |
---------------------------------------

Moje pytania:

Czy są jakieś systemy kompilacji uwzględniające w harmonogramie względne oczekiwane czasy zadań?
Jakie istnieją badania naukowe dotyczące tego rodzaju systemów kompilacji?
Skąd te systemy kompilacji (jeśli istnieją) pobierają informacje o czasie? Heurystyka, czasy zebrane podczas poprzednich kompilacji?
Jeśli takie systemy kompilacji nie istnieją, dlaczego? Czy istnieje gotcha, która sprawiłaby, że byłyby mniej wartościowe niż się wydaje na pierwszy rzut oka?

scheduling research build-system sjakobi
źródło

Większość pytań dotyczących zasobów lub narzędzi stron trzecich jest szybko zamykana jako „nie na temat”, ale myślę, że to może być przypadek, który wydaje się dobrze pasować do zakresu tej witryny.

Doc Brown

Myślę, że opiera się to na błędnym założeniu, że „budowanie” zadania nie jest równoległe.

Dagnelies

W większości przypadków zbudowanie zadania jest rzeczywiście nierównoległe, ale tak, np. Testy jednostkowe w aplikacjach wielowątkowych mogą być rzeczywiście równoległe. W rzeczywistości w projekcie, w którym pracuję, musimy zawsze wywoływać „make” z „-j1” do uruchomienia testu jednostkowego, ponieważ w przeciwnym razie testy jednostkowe związane z wydajnością zawodzą.

juhist

@juhist Jeśli chcesz przejść na bardziej ekspresyjny system kompilacji, shake ma koncepcję zasobów, w której możesz na przykład określić, ile rdzeni procesora powinno być zarezerwowanych do testów jednostkowych.

sjakobi

Odpowiedzi:

Microsoft Visual Studio Team System (wcześniej TFS) bierze pod uwagę czasy akcji kompilacji i kompilacje równoległe; pobiera dane z poprzedniej historii kompilacji; i chociaż nie wierzę, że możesz uzyskać pożądane zachowanie po wyjęciu z pudełka, możesz być w stanie go dostosować.

Przykład niektórych niestandardowych zadań do pracy nad optymalizacją wydajności

https://veegens.wordpress.com/2013/03/26/tfs-2010-build-performance-report/

Bruno Guardia
źródło

Jeśli dobrze rozumiem twoją odpowiedź i link, zgłaszane są czasy działania kompilacji (co jest raczej powszechną funkcją), ale nie jest jasne, czy i jak można wykorzystać te czasy do poprawy harmonogramu kompilacji. To tak naprawdę nie odpowiada na moje pierwotne pytanie, więc nie przyznam nagrody za twoją odpowiedź.

sjakobi

Nie ma problemu, możesz przegapić to, że możesz dostosować akcje kompilacji i proces kompilacji, poprzez programowanie. Próbka raportowała, ale jak już wspomniano, historia jest pobierana do automatycznych optymalizacji. Pamiętaj też, że możesz skonfigurować kompilacje równoległe. Ale aby upewnić się, że są one równoległe zgodnie z algorytmem, konieczne może być dostosowanie za pomocą kodu. Dodatkowe informacje: dotnetcurry.com/visualstudio/1177/…

Bruno Guardia

@BrunoGuardia: czy możesz wyjaśnić, gdzie w tym artykule linku jest wymieniona opcja dostosowywania, która mogłaby pomóc w wykorzystaniu przewidywanych czasów zadań akcji kompilacji?

Doc Brown

Opiera się to na błędnym założeniu, że „budowanie” zadania nie jest równoległe.

Wiele kompilatorów działa wielowątkowo, więc jedno zadanie A będzie wykorzystywać wszystkie procesory. Dlatego kolejność nie ma znaczenia. W przypadku zadań związanych z operacjami we / wy, zwłaszcza związanych z tworzeniem sieci, lepiej rozpocząć je wszystkie równolegle od samego początku: większość czasu będzie poświęcana na oczekiwanie na odpowiedź.

Innymi słowy, kolejność nie ma znaczenia, ponieważ poszczególne zadania są zwykle równoległe (jak na przykład kompilacja)

Edytować:

W rzeczywistości ta koncepcja „Zadania A na CPU 1” jest również wadliwa. Nawet w przypadku zadań jednowątkowych system operacyjny planujący procesy / wątki może przeskakiwać z procesora na procesor na każdym przełączniku kontekstowym. Wydaje mi się, że większość systemów kompilacji po prostu uruchamia wszystkie zadania równolegle i pozwala systemowi operacyjnemu wykonać harmonogram. Dłuższe zadania potrwają dłużej i tyle.

Zakładając, że masz długo działające jedno wątkowe zadanie, które nie jest związane z operacjami we / wy , systemowi kompilacji byłoby znacznie łatwiej przypisać mu priorytet / ważność, zamiast próbować opóźniać mniejsze zadania w celu ograniczenia przełączania kontekstu z systemu operacyjnego.

Nawet jeśli masz tak dziwne zadania, co jest dość rzadkie w praktyce, i masz fantazyjny system kompilowania harmonogramów, który działa na heurystyce w oparciu o poprzednie przebiegi (jedyny sposób, aby się dowiedzieć), korzyści, które możesz z tego uzyskać, mogą być niewielkie. . jednak masz do czynienia z dodatkową złożonością.

Dagnele
źródło

Równoległość „w ramach zadania” jest interesującym aspektem i z pewnością oferuje dodatkowy potencjał optymalizacji, ale nie sądzę, że zakładanie, że każde zadanie będzie się skutecznie skalować do dowolnej liczby procesorów, jest lepsze niż zakładanie, że każde zadanie musi działać na pojedynczy rdzeń.

sjakobi

@sjakobi: cóż, w praktyce bardzo ważne jest, aby kompilatory były wydajne. Czy możesz sobie wyobrazić, że długo czekasz na kompilację, ponieważ używany jest tylko 1 z 16 rdzeni? To nie da się. Przy całej teorii wydaje się, że przeoczasz rzeczywistość. Planowanie jest bardzo interesującym i bardzo znaczącym tematem. Jest to po prostu IMHO stosunkowo bezużyteczne w kontekście systemów kompilacji. Znowu większość kompilatorów i tak jest obecnie wielowątkowych ... a jeśli nie są, należy raczej włożyć wysiłek w ten system kompilacji planowania.

Dagnele

Wszystkie kompilatory wolnego oprogramowania ( GCC i Clang ...) dla C ++ lub C lub Fortran lub Ada są monowątkowe. make -jKompilacja system ( ) może równolegle uruchamiać kilka procesów kompilacji.

Basile Starynkevitch

@BasileStarynkevitch: ... rzeczywiście. Zasadniczo wszyscy rozsądni używają, -j <nb-cores>ale niestety domyślną wartością jest wciąż „1” ... Nadal jestem zaskoczony, że nigdy się nie zmieniła.

Dagnele

@dagnelies: Istnieje ogromna liczba plików Makefile, które pomijają niektóre krytyczne zależności i dlatego nie działają (lub mogą nie działać) z -jN, gdzie N> 1.

juhist