Pytania dotyczące algorytmów lub programów obliczających jednocześnie na wielu procesorach. Nie należy mylić z przetwarzaniem współbieżnym lub rozproszonym!
Kilka lat temu MapReduce został okrzyknięty rewolucją programowania rozproszonego. Byli też krytycy, ale ogólnie był entuzjastyczny szum. Zostało nawet opatentowane! [1] Nazwa nawiązuje mapi reduceprogramowania funkcjonalnego, ale kiedy czytam (Wikipedia) Krok mapy: węzeł główny pobiera dane...
Często słyszę ludzi mówiących o obliczeniach równoległych i obliczeniach rozproszonych , ale mam wrażenie, że nie ma wyraźnej granicy między tymi dwoma, a ludzie dość łatwo mylą to, podczas gdy uważam, że jest zupełnie inaczej: Obliczenia równoległe są ściślej powiązane z wielowątkowością lub...
Patrząc na programowanie współbieżne, powszechnie stosuje się dwa terminy, tj. Współbieżny i równoległy. Niektóre języki programowania w szczególności twierdzą, że obsługują programowanie równoległe, takie jak Java . Czy to oznacza, że programowanie równoległe i współbieżne faktycznie się...
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void...
Czy istnieje jakiś algorytm, który jest bardzo trudny do zrównoleglenia lub badania są nadal aktywne? Chciałem wiedzieć o każdym algorytmie lub polu badań w obliczeniach równoległych. Wszystko, czego szukałem, ma „równoległą” implementację. Po prostu chcę zrobić trochę badań na dowolnym...
Niedawno czytałem o algorytmach sprawdzania podobieństwa i czytałem, że problem jest P-zupełny . Co więcej, konsekwencją tego jest to, że ten problem lub jakikolwiek problem P-zupełny prawdopodobnie nie będzie miał wydajnych algorytmów równoległych. Jaka jest intuicja stojąca za tym ostatnim...
Miałem problemy z zaakceptowaniem złożonego poglądu teoretycznego na „efektywnie rozwiązany algorytm równoległy”, który podaje klasa NC : NC klasa problemów, które mogą zostać rozwiązane przez algorytm równoległym w czasie o p ( n ) ∈ O ( n k ) procesory c , k ∈ N .O ( logdon...
Zastanawiam się, czy obecnie masowo równoległe jednostki obliczeniowe dostępne w kartach graficznych ( na przykład programowalne w OpenCL ) są wystarczająco dobre, aby skutecznie symulować automaty komórkowe 1D (a może automaty komórkowe 2D?). Jeśli wybierzemy dowolną skończoną siatkę, która...
Rozważ następujący bardzo prosty program komputerowy: for i = 1 to n: y[i] = x[p[i]] Tutaj i y są n -elementowe tablice bajtów, a P jest N -elementowe szereg słów. Tutaj n jest duże, np. N = 2 31 (tak, że tylko niewielka część danych mieści się w jakiejkolwiek pamięci...
Powiedzmy, że mamy duży zbiór zadań i zbiór identycznych (pod względem wydajności) procesorów które działają całkowicie w równolegle. W przypadku interesujących scenariuszy możemy założyć . Każde zajmuje pewną ilość czasu / cykli, gdy jest przypisane do procesora , a po przypisaniu nie można go...
Mam wiele powiązanych pytań dotyczących tych dwóch tematów. Po pierwsze, większość tekstów złożoności tylko tuszować klasę . Czy istnieje dobry zasób, który bardziej szczegółowo omawia badania? Na przykład coś, co omawia wszystkie moje pytania poniżej. Ponadto, jestem przy założeniu, że N C nadal...
Myślałem, że to pytanie jest lepiej obsługiwane w części CS programu Stack Exchange. Teraz, gdy mamy GPGPU z takimi językami jak CUDA i OpenCL, czy rozszerzenia multimediów SIMD (SSE / AVX / NEON) nadal spełniają swoje zadanie? Niedawno przeczytałem artykuł o tym, jak można zastosować instrukcje...
Zaimplementowałem sortowanie topologiczne na podstawie artykułu z Wikipedii, którego używam do rozwiązywania zależności, ale zwraca ono listę liniową. Jakiego algorytmu mogę użyć do znalezienia niezależnych
Próbuję rozwiązać problem SAT z 25k klauzul 5k zmiennych. Ponieważ działa od godziny (precosat), a potem chciałbym rozwiązać większe, szukam wielordzeniowego SAT-Solvera. Ponieważ wydaje się, że jest wiele rozwiązań SAT, jestem całkiem zagubiony. Czy ktoś mógłby wskazać mi najlepszy dla mojej...
Zostaliśmy zaprezentowani w klasie z algorytmem znajdowania maksimum w tablicy równolegle w złożoności czasowej z komputerami.O ( 1 )O(1)O(1)n2)n2)n^2 Algorytm był: Biorąc pod uwagę tablicę A o długości n: Utwórz tablicę flag B o długości n i zainicjuj ją zerami z komputerów.nnn Porównaj...
Wymagane jest znalezienie mocy (dodatniej liczby całkowitej) macierzy liczb rzeczywistych. Istnieje wiele wydajnych algorytmów mnożenia macierzy (np. Niektóre algorytmy równoległe to Cannon, DNS ), ale czy istnieją algorytmy, które są przeznaczone właśnie do znalezienia mocy macierzy i które są...
Próbując poprawić wydajność mojej klasy wykrywania kolizji, odkryłem, że ~ 80% czasu spędzonego na GPU spędza na warunkach, jeśli tylko próbuję ustalić granice wiader, przez które powinna się zapętlać. Dokładniej: każdy wątek otrzymuje identyfikator, przez ten identyfikator pobiera swój trójkąt...
Czy algorytm sztucznej sieci neuronowej można wyrazić w kategoriach operacji zmniejszania mapy? Interesuję się również bardziej ogólnie metodami paralelizacji stosowanymi do ANN i ich zastosowaniem do przetwarzania w chmurze. Sądzę, że jedno podejście wymagałoby uruchomienia pełnego ANN na każdym...
Załóżmy, że chcemy połączyć dwie relacje w predykacie. Czy to jest w NC? Zdaję sobie sprawę, że dowód, że nie ma go w NC, będzie równoznaczny z dowodem, że , więc przyjmuję dowód, że jest to otwarty problem jako odpowiedź.P≠NCP≠NCP\not=NC Interesuje mnie zarówno ogólny przypadek, jak i konkretne...
W Dowodach i typach Girarda możemy przeczytać: Z algorytmicznego punktu widzenia rachunek sekwencyjny nie ma izomorfizmu Curry'ego-Howarda ze względu na wiele sposobów pisania tego samego dowodu. To uniemożliwia nam użycie go jako maszynopisu -calculus, chociaż dostrzegamy jakąś głęboką...