Autor: Andrzej Lewandowski (lewando_at_ibm.net)
Data: Thu 05 Mar 1998 - 04:02:08 MET
Krzysztof Halasa <khc_at_intrepid.pm.waw.pl> wrote:
>lewando_at_ibm.net (Andrzej Lewandowski) writes:
>> >Czyli Twoj problem obliczeniowy duzo sie synchronizuje, i nie da sie tego
>> >poprawic.
>>
>> Na ogol tak wlasnie jest w programowaniu rownoleglym. Cala sztuka to
>> tak sformulowac algorytm zeby sie dalo.
>Roznie jest - czasem jest tak, a czasem synchronizacja prawie nie
>kosztuje. Chociaz tutaj pewnie bedzie ten pierwszy przypadek.
Niekoniecznie zaraz synchronizacja. Czasami wlasciwosci samego
problemu (nawet rozwiazywanego na idealnej teoretycznej maszynie
rownoleglej zwanej PRAM) nie pozwalaja na uzyskanie liniowego
przyspieszenia. Prykladem sa algorytmy "divide and conquer" ktore w
oryginalnym sformulowaniu nie pozwalaja na uzyskanie przyspieszenia
lepszego niz logarytmiczne.
>> Zalezy. W tym ktory wymaga obliczen rownoleglych ok. 20 zrodel, 2000
>> punktow dostaw, 20 tysiecy zamowien dziennie. Sa wieksze problemy niz
>> ten, i mniejsze.
>A tak wlasciwie, dlaczego to jest takie duze i dlaczego w smalltalku?
Dlatego ze w Smalltalku robi sie 100 razy szybciej niz w... Nie mowiac
ze przyjemniej.
>Bo o ile zlozonosc obliczeniowa takich problemow jest generalnie
>znaczna (nie pamietam dokladnie, nie zajmuje sie teraz niczym takim),
>to sam algorytm poszukiwania rozwiazania jest dosyc prosty. Oczywiscie
>zalezy to od tego, jaki to algorytm, ale to jest nieco bardziej
>rozwiniety klasyczny traveling salesman problem, i jestem pewien,
>ze daloby sie to zrobic prosto.
No dziekuje - salesman prosty... Ale dla jakiej wymiarowosci jest on
prosty? Na dodatek to nie jest travelling salesman, tylko cos co sie
mazywa "multiple-depot periodic vehicle routing". Niewiele ma
wspolnego z salesmanem, i metodami specyficznymi dla salesmana nie da
sie go rozwiazac. W ogolnosci, bardzo malo jest wiadomo na temat
dobrych metod rozwiazywania tego problemu, zwlaszcza takich o
wymiarowosci "wzietej z zycia". Jezeli potrafisz to zrobic prosto -
prosze bardzo, zrob, napisz papier - slawa (i pieniadze) gwarantowane.
Jak chcesz sie doszkolic to poszukaj na AltaVista hasla "parallel tabu
search" i "vehicle routing".
>Oczywiscie, sam algorytm to nie wszystko, ale w takim razie jest
>to raczej prezentacja/bazy_danych/zarzadzanie + maly kawalek kodu
>(liczacy sie dlugo) na TSP.
To nie jest MALY kawalek kodu.
>No i na pewno ten kawalek kodu da sie zrobic na czyms innym niz
>NT, bedzie to dzialac wydajniej, i bedzie tansze. I niekoniecznie
>musi byc to Linux, chociaz on z pewnoscia tez ma takie cechy.
Nie da sie, bo trzeba by wszystkie obiekty przekonwertowac do jakiejs
takiej postaci zeby "to cos innego" moglo je zrozumiec. Co by bylo
dosyc kosztowna operacja. Probowano, a jakze. A tak na marginesie,
probowano tez "cos innego". Pod UNIXem, a jakze. Nie NT, nie Wintel.
Za 10 albo 20 razy wiecej pieniedzy. 2 - 3 razy wolniej. A na pewno
nie szybciej.
A.L.
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 17:04:25 MET DST