Pierwszą rzeczą, na którą należy zwrócić uwagę w związku z tym problemem, jest to, jakie dane są potrzebne gdzie i kiedy. Aby to zrobić, zwykle zaczynam od głupiej, seryjnej wersji problemu.
Znajdź wszystkie działki o wartości powyżej x $ / akr, które znajdują się w odległości y stóp od innej działki o wartości mniejszej niż z $ / akr.
foreach p in parcels {
if value(p) > x {
foreach q in parcels {
if (dist(p,q) <= y) and (value(q) < z) {
emit(p)
}
}
}
}
Chociaż ten algorytm nie jest zoptymalizowany, rozwiąże problem.
Podobny problem rozwiązałem w mojej pracy magisterskiej, która znalazła najbliższą paczkę dla każdego punktu w zbiorze danych. Zaimplementowałem rozwiązanie w PostGIS , Hadoop
i MPI . Pełna wersja mojej pracy dyplomowej jest tutaj , ale podsumuję ważne punkty, które dotyczą tego problemu.
MapReduce nie jest dobrą platformą do rozwiązania tego problemu, ponieważ wymaga dostępu do całego zestawu danych (lub starannie wybranego podzbioru) w celu przetworzenia pojedynczej paczki. MapReduce nie radzi sobie dobrze z dodatkowymi zestawami danych.
MPI może jednak całkiem łatwo to rozwiązać. Najtrudniejsze jest określenie sposobu podziału danych. Podział ten opiera się na ilości danych, liczbie procesorów, na których trzeba je uruchomić oraz ilości pamięci na procesor. Aby uzyskać najlepsze skalowanie (a tym samym wydajność), musisz mieć jednocześnie wiele kopii zestawu danych paczek w pamięci (na wszystkich komputerach).
Aby wyjaśnić, jak to działa, założę, że każdy z 50 komputerów ma 8 procesorów. Następnie przypiszę każdemu komputerowi odpowiedzialność za sprawdzenie 1/50 paczek. To sprawdzenie zostanie wykonane przez 8 procesów na komputerze, z których każdy ma kopię tej samej 1/50 części paczek i 1/8 zestawu danych paczki. Należy pamiętać, że grupy nie są ograniczone do jednego komputera, ale mogą przekraczać granice komputera.
Proces wykona algorytm, uzyskując paczki dla p z 1/50 zestawu paczek, a paczki dla q z 1/8 zestawu. Po wewnętrznej pętli wszystkie procesy na tym samym komputerze będą ze sobą rozmawiać, aby ustalić, czy paczka powinna zostać wysłana.
Zaimplementowałem algorytm podobny do tego dla mojego problemu. Możesz znaleźć źródło tutaj .
Nawet z tego rodzaju niezoptymalizowanym algorytmem byłem w stanie uzyskać imponujące wyniki, które były wysoce zoptymalizowane pod kątem czasu programisty (co oznacza, że mogłem napisać głupi prosty algorytm, a obliczenia nadal byłyby wystarczająco szybkie). Następnym miejscem do zoptymalizowania (jeśli naprawdę jest to potrzebne) jest ustawienie indeksu poczwórnego drugiego zestawu danych (skąd otrzymujesz q z) dla każdego procesu.
Aby odpowiedzieć na oryginalne pytanie. Istnieje architektura: MPI + GEOS. Dodaj trochę pomocy z mojej implementacji ClusterGIS i całkiem sporo można zrobić. Całe to oprogramowanie można znaleźć jako oprogramowanie typu open source, więc nie ma opłat licencyjnych. Nie jestem pewien, jak przenośny jest dla systemu Windows (może z Cygwinem), ponieważ pracowałem nad nim w systemie Linux. To rozwiązanie można wdrożyć w EC2, Rackspace lub dowolnej dostępnej chmurze. Kiedy go opracowałem, korzystałem z dedykowanego klastra obliczeniowego na uniwersytecie.