Apakah ada arsitektur untuk geoproses terdistribusi?

24

Misalkan saya memiliki 50 komputer di LAN saya. Setiap komputer memiliki geodatabase untuk semua poligon paket di negara bagian tertentu di AS.

Aku ingin menulis tugas geoprocessing yang menemukan semua paket bernilai lebih dari x $ / acre yang berada dalam y kaki dari paket lain yang bernilai kurang dari z $ / acre.

Saya ingin merumuskan dan menjalankan kueri ini tanpa mengetahui atau peduli bahwa data didistribusikan di 50 komputer. Ingatlah syarat-syarat batas: Saya juga ingin kueri mengembalikan kasus di mana paket mahal di satu negara dekat paket murah di negara lain.

Apakah ada arsitektur yang mendukung semacam ini geoprocessing terdistribusi?

Arsitektur dapat dijelaskan secara abstrak, atau sebagai implementasi khusus untuk Azure atau Amazon Web Services. Atau, lebih disukai, sebagai kantor biasa tempat komputer duduk diam di malam hari dengan lisensi desktop ArcGIS yang berlimpah.

geoprocessing cloud-gis amazon-web-services Kirk Kuykendall
sumber
1
Pertanyaan yang bagus Dalam contoh khusus ini Anda memerlukan cara untuk secara otomatis memaralelkan bangunan dan penggunaan struktur data spasial seperti quadtree. Jika Anda tidak melakukannya, dan sebagai gantinya hanya mendistribusikan pencarian brute-force lebih dari 50 komputer, Anda mungkin sebenarnya memperlambat permintaan daripada mempercepatnya. Saya cukup yakin arsitektur umum seperti ini belum ada, jadi Anda mungkin lebih beruntung dengan terlebih dahulu merenungkan jenis pertanyaan apa yang mungkin mendapat manfaat dari pemrosesan terdistribusi dan kemudian melihat ke dalam arsitektur yang mereka butuhkan. Mungkin memposting pertanyaan ini di situs TCS?
whuber
@whuber Terima kasih, apa situs TCS?
Kirk Kuykendall
@Kirk maaf karena samar - saya malas. cstheory.stackexchange.com
whuber
1
teori CS dasar mungkin tidak akan membantu karena orang-orang CS jarang mendapatkan spasial :-)
Ian Turton
1
@iant Tidak ada terlalu banyak orang GIS di luar sana yang akan tahu banyak tentang mur dan baut dari komputasi terdistribusi (saya tidak melemparkan aspirasi pada anggota situs ini yang jelas luar biasa). Saya percaya orang-orang TCS akan memiliki pengetahuan untuk menjawab pertanyaan awal mengenai keberadaan arsitektur. Satu-satunya kekhawatiran saya adalah apakah mereka akan menemukan pertanyaan yang menarik! Saya pikir jika itu dilakukan dengan cara yang benar, mereka mungkin. (Misalnya, orang mungkin membingkai ulang dalam hal struktur data.)
whuber

Jawaban:

13
  1. simpan semua paket Anda dalam satu basis data pusat
  2. merumuskan kisi-kisi di atas AS yang terbuat dari kotak N kaki di satu sisi, di mana N sedemikian rupa sehingga jumlah paket yang sesuai dengan N tidak akan mengeluarkan memori pada salah satu node Anda
  3. buat tabel di database Anda dengan satu baris per kotak kisi, kolom id kolom geometri dan kolom status
  4. setiap node menjalankan program kecil itu
    1. temukan kotak yang belum diproses berikutnya
    2. menandainya sebagai dalam proses
    3. menarik semua paket ST_DWithin (persegi, parsel, maxfeet)
    4. melakukan permintaan aktual
    5. menulis kembali jawaban kueri ke tabel solusi di database pusat
    6. menandai persegi sebagai lengkap
    7. kembali ke 1

Kasus kegagalan yang jelas adalah ketika radius Anda dalam kueri parsel tumbuh cukup besar sehingga sebagian besar dataset Anda adalah kandidat potensial yang cocok dengan setiap parsel.

Paul Ramsey
sumber
Terima kasih Paul, apakah saya memerlukan satu simpul yang bertindak sebagai koordinator untuk simpul lainnya?
Kirk Kuykendall
Basis data bertindak sebagai "koordinator" implisit karena memegang status antrian, tetapi node tidak perlu dikoordinasikan di luar dimulai dan diarahkan ke database. Tidak yakin apakah itu jawaban atau tidak.
Paul Ramsey
7

Ada slot menarik di FOSS4G pada bulan September di Barcelona tentang ini: http://2010.foss4g.org/presentations_show.php?id=3584

Itu menjadi lebih dari diskusi panel daripada presentasi.

Di tengah posting blog ini Paul Ramsey memberikan semacam ringkasan dari itu.

Nicklas Avén
sumber
Itu terlihat menjanjikan, sudahkah mereka memposting presentasi di mana saja?
Kirk Kuykendall
Yah, karena Schuyler Erle menjadi moderator untuk diskusi panel alih-alih mengubah rencana presentasi yang direncanakan, saya tidak berpikir akan ada lebih banyak informasi tentang itu. Tetapi karena Erle telah merencanakan presentasi itu, ia mungkin memiliki beberapa informasi tentangnya. Dia ada di mana-mana jika Anda melakukan pencarian google. Mungkin ide untuk bertanya langsung padanya. Saya tidak tahu Sebagian besar diskusi berada di atas pemahaman saya sehingga saya tidak dapat memberikan resume yang lebih baik daripada yang dilakukan Paul di blognya.
Nicklas Avén
4

Mungkin lihat pada kertas putih "ArcGIS Server dalam Seri Praktek: Geocoding Batch Besar" di kertas putih esri .

Ini tentang geocoding tetapi proses umum menggunakan layanan geoprocessing asinkron mungkin berlaku untuk kasus Anda.


sumber
Terlihat bagus, saya bertanya-tanya apakah ini dapat digeneralisasi ke bentuk lain dari geoprocessing. Sepertinya saya perlu tumpang tindih antara dataset saya.
Kirk Kuykendall
3

Hal pertama yang harus diperhatikan tentang masalah ini adalah data apa yang dibutuhkan di mana dan kapan. Untuk melakukannya, saya biasanya mulai dengan versi serial masalah yang bodoh.

Temukan semua paket bernilai lebih dari x $ / acre yang berada dalam y kaki dari paket lain yang dihargai kurang dari z $ / acre.

foreach p in parcels {
  if value(p) > x {
    foreach q in parcels {
      if (dist(p,q) <= y) and (value(q) < z) {
        emit(p)
      }
    }
  }
}

Meskipun algoritma ini tidak dioptimalkan, itu akan menyelesaikan masalah.

Saya memecahkan masalah yang sama untuk tesis Master saya yang menemukan paket terdekat untuk setiap poin dalam dataset. Saya mengimplementasikan solusi di PostGIS , Hadoop , dan MPI . Versi lengkap dari tesis saya ada di sini , tetapi saya akan merangkum poin-poin penting yang berlaku untuk masalah ini.

MapReduce bukan platform yang baik untuk menyelesaikan masalah ini karena membutuhkan akses ke seluruh dataset (atau subset yang dipilih dengan cermat) untuk memproses paket sin gle. MapReduce tidak menangani dataset sekunder dengan baik.

Namun, MPI dapat menyelesaikannya dengan cukup mudah. Bagian tersulit adalah menentukan cara membagi data. Pemisahan ini didasarkan pada berapa banyak data yang ada, berapa banyak prosesor yang harus Anda jalankan, dan berapa banyak memori yang Anda miliki per prosesor. Untuk penskalaan terbaik (dan karenanya kinerja), Anda harus memiliki beberapa salinan dataset paket dalam memori (di semua komputer Anda) sekaligus.

Untuk menjelaskan cara kerjanya, saya akan berasumsi bahwa masing-masing dari 50 komputer Anda memiliki 8 prosesor. Saya kemudian akan menugaskan masing-masing komputer tanggung jawab untuk memeriksa 1/50 dari paket. Pemeriksaan ini akan dilakukan oleh 8 proses di komputer, yang masing-masing memiliki salinan 1/50 bagian dari paket dan 1/8 dari dataset paket. Harap dicatat bahwa grup tidak terbatas pada satu mesin saja, tetapi dapat melewati batas mesin.

Proses ini akan menjalankan algoritma, mendapatkan parsel untuk p dari set parsel 1/50, dan parsel untuk q dari set 1/8. Setelah loop dalam, semua proses pada komputer yang sama akan berbicara bersama untuk menentukan apakah paket tersebut harus dipancarkan.

Saya menerapkan algoritma yang mirip dengan ini untuk masalah saya. Anda dapat menemukan sumbernya di sini .

Bahkan dengan algoritma yang tidak dioptimalkan semacam ini saya dapat memperoleh hasil yang mengesankan yang sangat dioptimalkan untuk waktu programmer (yang berarti bahwa saya bisa menulis algoritma sederhana yang bodoh dan komputasinya masih cukup cepat). Tempat berikutnya untuk mengoptimalkan (jika Anda benar-benar membutuhkannya), adalah untuk mengatur indeks quadtree dari dataset kedua (di mana Anda mendapatkan q dari) untuk setiap proses.

Untuk menjawab pertanyaan awal. Ada arsitektur: MPI + GEOS. Lemparkan sedikit bantuan dari implementasi ClusterGIS saya dan cukup banyak yang bisa dilakukan. Semua perangkat lunak ini dapat ditemukan sebagai sumber terbuka, sehingga tidak ada biaya lisensi. Saya tidak yakin bagaimana portabel untuk Windows itu (mungkin dengan Cygwin) karena saya bekerja di linux. Solusi ini dapat digunakan pada EC2, Rackspace, atau cloud apa pun yang tersedia. Ketika saya mengembangkannya saya menggunakan cluster komputasi khusus di sebuah Universitas.

Nathan Kerr
sumber
2

Metodologi pemrograman paralel sekolah tua adalah hanya menyimpan keadaan + paket yang menyentuhnya pada setiap prosesor maka memalukan mudah untuk diparalelkan. Tetapi mengingat variasi ukuran negara bagian AS Anda akan mendapatkan kinerja yang lebih baik dengan memecah negara menjadi sel-sel grid (sekali lagi dengan lingkaran hal menyentuh) dan mengirimkan setiap sel grid ke prosesor menggunakan konfigurasi master slave.

Ian Turton
sumber
Alih-alih parsel yang bersentuhan, saya membutuhkan parsel dari negara bagian yang berdekatan dalam jarak y.
Kirk Kuykendall
Saya menganggap Y cukup kecil sehingga tidak signifikan lebih besar dari sejumlah kecil paket. Jika itu adalah sebagian besar dari keadaan maka Anda mungkin lebih baik menggunakan grid arbitrer untuk melakukan perhitungan.
Ian Turton
2

Anda mungkin ingin memberi tampilan pada Appistry . Ini dimaksudkan untuk memungkinkan migrasi aplikasi yang sudah ada ke infrastruktur cloud pribadi. Mungkin ada proyek lain dengan tujuan yang sama: daripada mencari tahu lagi dan lagi untuk setiap aplikasi kacang yang sangat kompleks dari mogok dan mendistribusikan tugas ke pemrosesan paralel, membuat perpustakaan atau platform yang melakukan itu secara otomatis.

matt wilkie
sumber
Terima kasih Matt, itu memang terlihat menjanjikan. Googling saya menemukan presentasi ini dari FedUC 2008 proceedings.esri.com/library/userconf/feduc08/papers/... aku akan penasaran untuk melihat update pada apa yang mereka lakukan sejak saat itu.
Kirk Kuykendall
2

Untuk jenis masalah ini, saya akan menggunakan kerangka peta / pengurangan. Kerangka kerja Appistry "mentah" bagus untuk masalah "paralel yang memalukan", yang dekat dengan ini. Kondisi tepi tidak memungkinkan. Map / Reduce (pendekatan Google untuk komputasi terdistribusi) sangat bagus untuk masalah jenis ini.

Kemajuan terbesar di Appistry sejak kertas 08 adalah rilis produk CloudIQ Storage. Ini memungkinkan untuk fasilitas penyimpanan "s3" seperti memanfaatkan disk pada server lokal Anda. Kemudian, produk CloudIQ Engine dapat mengaktifkan layanan volume tinggi atau menyebarkan / mengumpulkan aplikasi gaya apa pun (kami telah membuktikan skalabilitas menggunakan runtime ESRI dan lib sumber terbuka lainnya). Jika Anda beroperasi pada data berbasis file, Anda mendistribusikannya menggunakan CloudIQ Storage, dan merutekan pekerjaan pemrosesan ke replika file lokal sehingga tidak harus dipindahkan di jaringan. (jadi setiap node tidak memerlukan semua data)

Untuk Map / Reduce, Anda dapat melapisi sesuatu seperti Hadoop (kerangka kerja M / R open source) pada CloudIQ Storage. Saya akan melihat Hadoop untuk masalah seperti yang dijelaskan, tetapi Anda benar-benar perlu menyelam, tidak mudah untuk memulai, dan M / R adalah penyok otak. Ada juga distribusi yang didukung secara komersial yang ditawarkan oleh Cloudera. Ada produk Appistry lain, CloudIQ Manger yang merupakan pelengkap yang bagus untuk Hadoop (Cloudera atau lainnya) untuk distribusi dan manajemen.

Saya akan mulai dengan Hadoop (M / R dan filesystem HDFS), dan jika Anda membutuhkan solusi yang dapat diskalakan yang didukung secara komersial, lihat Appistry CloudIQ Manager and Storage, bersama dengan distro Cloudera Hadoop.

Jika Anda menginginkan arsitektur yang lebih sederhana untuk tugas "memalukan paralel", lihat juga CloudIQ Engine. (pendekatan yang diuraikan dalam makalah yang dirujuk oleh Kirk masih berlaku)


sumber