Derinlik Grafik Hesaplama Sisteminin İlerlemesi ve Beklentisi
Büyük ölçekli grafik verilerinin madenciliği, mevcut iş operasyonlarını geliştirebilir ve hatta yeni iş modelleri oluşturabilir. Bununla birlikte, bu grafik verilerinin ölçeği, grafik veri madenciliğinin kendisini bir sorun haline getirir.Bu olağanüstü zorlukların tümü, büyük ölçekli grafik hesaplama ve yüksek ölçeklenebilirlik ile işleme için etkili araçların geliştirilmesine işaret eder. Bu makale önce grafik hesaplama teknolojisinin birkaç temel yönünü açıklıyor ve ardından Huawei'nin Nuh'un Gemisi Laboratuvarı'nın VENUS grafik hesaplama sistemini tanıtıyor ve son olarak grafik hesaplamanın gelişme eğilimi hakkında kısa bir bakış sunuyor.
arka fon
Birbirleriyle etkileşime giren çok sayıda farklı bireyin ürettiği veriler, grafikler halinde temsil edilir ve iletişim, İnternet, e-ticaret, sosyal ağlar ve Nesnelerin İnterneti alanlarında büyük miktarda grafik verisi toplanmıştır. Ölçeği çok büyük ve büyüyor. Kısaca bir grafik, düğümlerden (yani bireylerden) ve kenarlardan (yani bireyler arasındaki bağlantılardan) oluşur ve grafik verileri, farklı alanlardaki verilerde bu grafik yapısının ilgili kısımlarıdır. Web sayfaları ve sayfalar arasındaki köprülerin oluşturduğu grafiğin veya bir sosyal ağdaki farklı kullanıcılar ve kullanıcılar arasındaki ilişkiler zincirinin (bkz. Şekil 1) tümü büyük ölçekli grafik verilerini oluşturur. CNNIC istatistiklerine göre, yalnızca Çin'deki web sayfalarının oluşturduğu grafiklerin ölçeği 2010 yılında 60 milyar düğüme ulaştı ve yıllık% 78,6 büyüme oranında artmaktadır. Facebook'un sosyal ağı 2011'de 800 milyon düğümü aştı ve Tencent QQ sosyal ağının şu anda 1 milyar düğüm ölçeği var. Telekomünikasyon endüstrisinde, Guangzhou'daki arayanlar ve aranan taraflardan oluşan grafik, yalnızca bir ayda 45 milyon düğümü ve 150 milyon kenarı ele aldı. Tanınmış ClueWeb verileri, tam miktarda Web sitesi ve web sayfası içerir. 2012'de yayınlanan veri seti 100 milyon düğüme ve 42,5 milyar kenara ulaştı ve yalnızca kenarların listesini depolayan disk dosyası 400 GB'ı aştı.
Şekil 1 Sosyal ağlardaki farklı kullanıcılar ve kullanıcılar arasındaki ilişki zinciri, büyük ölçekli grafik verileri oluşturur
Bu çok değerlidir: Bu büyük ölçekli grafik verilerinin madenciliği mevcut iş operasyonlarını geliştirebilir ve hatta yeni iş modelleri oluşturabilir. Bununla birlikte, bu grafik verilerinin ölçeği, grafik veri madenciliğinin kendisini bir sorun haline getirir. Örneğin, ClueWeb grafiğinin tam SimRank hesaplaması binlerce yıl gerektirir. Bu olağanüstü zorlukların tümü, büyük ölçekli grafik hesaplama ve yüksek ölçeklenebilirliğe sahip işleme için etkili araçların geliştirilmesine işaret ediyor.
Endüstri, yıllarca süren uygulamalardan sonra MapReduce ve Spark gibi ana akım büyük veri platformlarını geliştirmiş olsa da, grafik madenciliği görevi kendi benzersizliğine sahiptir: veriler arasındaki güçlü bağımlılık nedeniyle, dağıtılmış işleme modunun çeşitli makineler arasında sık sık gerçekleştirilmesi gerekir. Veri değişimi ve grafik madenciliği algoritması akışının kendisi birden çok yinelemeden oluşur. Bu nedenle, ana akım büyük veri platformlarının grafik madenciliği görevlerini işlemek için uygun olmadığı kabul edilmektedir ve grafik hesaplama tabanlı büyük veri analiz platformları, grafik madenciliği ve ilgili makine öğrenimi algoritmaları için yeni bir yöntem haline gelmiştir. Temsilcilerden biri, Google tarafından önerilen Pregel sistemidir. Google, veri işlemenin% 20'sinin Pregel kullanılarak uygulandığını ve grafik hesaplamanın başarılı bir veri madenciliği işleme çerçevesi olduğunu iddia ediyor. Ancak Google, Pregel'in açık kaynak kodunun özel uygulamasını yapmadı ve dış dünya Pregel'in uygulanmasını taklit etmek için yarışıyor. 2012 yılında, Carnegie Mellon Üniversitesi profesörü Carlos Guestrin, endüstride yaygın endişe uyandıran dağıtılmış bir GraphLab çerçevesi önerdi.
Guestrin'e göre GraphLab'in öneri sistemlerinde pek çok uygulaması vardır.Diğer ana uygulama alanları arasında İnternet dolandırıcılık tespiti ve saldırı tespiti yer almaktadır. GraphLab projesi, Carlos Guestrin'in sorumluluğu altındaki bağımsız bir ticari şirket olan GraphLab Inc'den ayrıldı. Mayıs 2013'te şirket, Madrona Venture Group ve NEA'dan 6,75 milyon ABD Doları tutarında para topladı ve Ocak 2015'te Seri B finansmanından 18,5 milyon ABD Doları daha aldı. Ağustos 2016'da, bu grafik hesaplama şirketi Apple tarafından yaklaşık 200 milyon dolara satın alındı. Büyük veri trendi altında grafik hesaplamanın önemini ve yapay zeka endüstrisinin gelişimindeki gerekliliğini göstermektedir.
Aşağıda, bu makale önce grafik hesaplama teknolojisinin çeşitli temel yönlerini genişletiyor, ardından Huawei'nin Noah's Ark Laboratuvarı'nın VENUS grafik hesaplama sistemini tanıtıyor ve son olarak grafik hesaplamanın gelişme eğilimine kısa bir bakış sunuyor.
Grafik hesaplama çekirdek teknolojisi
Büyük ölçekli grafik veri analizine duyulan ihtiyaçla birlikte, son yıllarda birçok grafik hesaplama sistemi ortaya çıkmıştır ve bunlardan önemli dönüm noktası çalışmaları şunlardır: Pregel, GraphLab ve GraphChi. Çeşitli dağıtılmış küme işleme görevlerini uygulamak için MapReduce gibi basit arayüz işlevleri aracılığıyla mevcut Hadoop / Spark büyük veri çerçevesine benzer şekilde, grafik hesaplamanın temel fikri, grafik madenciliği ve ilgili makine öğrenimi algoritmalarını soyut bir şekilde ifade etmek için "tepe noktası gibi düşünmek" kullanmaktır. , Böylece çeşitli veri madenciliği görevleri köşe programları yazmaya dönüştürülebilir ve mevcut grafik hesaplama sistemleri tarafından yürütülebilir.
Köşe programı, grafikteki köşelerin ve bitişik kenarların hesaplama durumunu hesaplar ve günceller. Bu hesaplama durumları ayrıca diğer köşe programları yürütüldüğünde çağrılır. Grafik hesaplama sistemi, BSP paralel mekanizmasına (Pregel) veya asenkron paralel mekanizmaya (GraphLab) göre hesaplama kümesindeki tüm köşe programlarını planlar ve anlık görüntü kurtarma gibi belirli hata tolerans mekanizmalarını ekler. Bu şekilde, grafik hesaplama görevleri otomatik olarak hataya dayanıklı paralel işleme sahip olur ve bu da veri madenciliği algoritmalarının ölçeklenebilirliğini büyük ölçüde geliştirir.
Spesifik olarak, grafik hesaplama sistemi tarafından önceden tanımlanmış bir sanal işlev güncellemesi, kullanıcı mantığını ifade eden bir köşe programını gerçekleştirmek için aşırı yüklenebilir. Bu nedenle, grafik hesaplama sistemi her köşe için bu işlevi çağırır. Güncelleme yöntemi, mevcut tepe noktası ve kenarı bilgilerine ve gelen kenarın tepe noktasına ve kenarına ilişkin bilgilere erişebilir; aynı zamanda, bir tepe noktasının ve ona bağlı kenarın ağırlığını değiştirebilir. Bir algoritmayı tamamlamak için grafik hesaplamasının çoklu yinelemelerinde, her yineleme, sistemin grafiğin her köşesinde güncelleme işlevinin yürütülmesini tamamlamasıdır. Pregel eşzamanlı yürütme modunu ve diğer nedenleri benimsediğinden, hız nispeten yavaştır Şu anda, GraphLab ve GraphChi, sırasıyla dağıtılmış grafik hesaplama sistemleri ve disk tabanlı bağımsız grafik hesaplama sistemleri için endüstri ölçütleri haline gelmiştir.
GraphLab, bellek tabanlı dağıtılmış bir grafik hesaplama sistemidir.Bir grafik birden çok alt grafiğe bölünür ve her alt grafik bir bilgisayarın belleğinde saklanır. Grafik, kesmek için köşeler seçilerek bölünür. Ayrıldıktan sonra, kesim grafiğinin seçilen köşeleri, bu köşelerle bitişik olan tüm farklı alt grafiklerle birleştirilir. Bu şekilde, aynı anda birden fazla ana bilgisayarda saklanan her kesme noktasının birden çok kopyası vardır. Bu nedenle, her grafik hesaplama yinelemesinde, her ana bilgisayar, ana bilgisayardaki alt grafiğin köşelerinde güncelleme işlevini yürütür ve her güncellenen köşenin hesaplama sonucu değerinin, diğer ana bilgisayarların tepe noktasının yedeği ile senkronize edilmesi gerekir. Grafik verileri, grafiğin köşelerini ve kenarlarını ve köşeler ve kenarlardaki değerleri içerir. Bu nedenle, GraphLab'in grafiğin yapı bilgisini iletmek için ağı kullanmasına gerek olmamasına rağmen, hesaplama sürecinde, GraphLab senkronizasyon tepe noktasının değerini iletmek için hala çok fazla ağ ek yüküne ihtiyaç duyar.
Carnegie Mellon Üniversitesi'nin GraphLab projesinden, hızla büyüyen bir dal atanır: GraphChi. Veri madenciliği algoritmalarını otomatik olarak harici bellek algoritmalarına ve çekirdek dışı işlemeye göre dönüştürür. Köşe merkezli hesaplama modelini işlemek ve yürütmek için grafiğin alt grafiklere bölünmesine gerek yoktur. Bu şekilde, bir PC bile büyük veri analizi görevinin üstesinden gelebilir. Disk tabanlı bağımsız bir grafik hesaplama sistemi olan GraphChi'de, bir grafik birden çok veri parçasına bölünür ve her veri parçasının bellekte depolanması garanti edilir. Her veri parçası, sürekli bir köşe aralığı ve bu köşelerin iç ve dış kenarları dahil olmak üzere eksiksiz bir alt grafik içerir. Disk tabanlı bağımsız grafik hesaplama sisteminin grafik hesaplaması da birden çok yinelemeden oluşur.Her yinelemede, sistem her bir köşe üzerinde kullanıcı tanımlı bir güncelleme işlevi yürütür. Her yinelemede, sistem her veri dilimini sırayla işler ve güncelleme işlevini her veri diliminde paralel olarak yürütür Paralellik, çok sayıda iş parçacığı arasında yalnızca tek makineli bir paralelliktir.
GraphChi'nin çözdüğü ana zorluklardan biri, veri madenciliği algoritmalarını tamamlamak için verimli I / O maliyetlerinin nasıl kullanılacağıdır. Grafik hesaplama modeline dayalı veri madenciliği algoritmasının verileri, grafikteki bilgiler olarak diskte depolandığından, bir yinelemenin genellikle tüm grafik modelinin veri depolamasını taraması gerekir. Bir taramada toplam | E | veri biriminin okunması gerekir, çünkü veriler grafiğin kenarlarına göre saklanır.Yani, bir yineleme en fazla | E | okuma ve yazma işlemlerine, yani 2 × | E | kez neden olabilir Disk G / Ç.
Bu sorunu çözmek için, GraphChinin temel fikri, diskteki düzenlemeyi ve gruplamayı grafik hesaplama modeliyle eşleşecek şekilde dikkatlice tasarlamaktır, böylece bu grafik hesaplama modeline dayalı herhangi bir veri madenciliği algoritması yalnızca P2 disk okuma işlemlerinde bir yinelemeyi tamamlayabilir ve P2 disk yazma işlemi. Bu mekanizma, grafiğin köşelerini köşe kimliğinin aralığına göre P parçalarına ayıran kayan pencere mekanizması (Parallel Sliding Window, PSW) olarak adlandırılır. Aralık tek tip değildir, ancak veri parçasının boyutu tek tiptir, bu nedenle aralığın boyutu, karşılık gelen veri parçasının boyutuna göre belirlenir. Veri dilimleme, aralıktaki her tepe noktası ve ona bağlı tüm gelen kenarlar tarafından oluşturulan tüm alt grafiklerin kümesidir. Yani, veri segmenti, aralıktaki köşelere işaret eden grafikteki tüm kenarları içerir ve bu kenarların sayısı temelde farklı veri segmentlerinde aynıdır. Veri parçasının kenarları ayrıca kaynak tepe noktasının kimliğine göre artan sırada düzenlenir. Veri diliminin boyutu, ana belleğin tutabileceği en büyük veri dilimiyle belirlenir. Bilgisayarın ana belleği, bellek hesaplamaları için tüm grafik verilerini barındıramadığında, GraphChi'nin grafik verileri için disk depolama tasarımı, grafik hesaplamalarının I / O verimli olmasını sağlar.
Bir grafik hesaplama algoritması sürecinde, GraphChi tek seferde ana belleğe bir parça veri okur, böylece karşılık gelen aralıktaki tüm köşelerin gelen kenarları kullanılabilir olur. Bu köşelerin giden kenarları, kalan P-1 veri dilimlerinde saklanmalıdır. Ve her veri segmentinin kenarları, kaynak tepe noktasının kimliğine göre artan sırada düzenlendiğinden, bu köşelerin giden kenarları her veri segmentinde sürekli bir alanda olmalıdır. Bu nedenle, hem gelen hem de giden kenarları olan bir köşe aralığındaki tüm alt grafikler, bir veri dilimi tam taraması ve P-1 veri dilimi kısmi taramasıyla tamamlanabilir. Bellekte elde edilen bu alt grafikler için, GraphChi aynı anda birden çok iş parçacığındaki farklı alt grafiklere dayalı hesaplama görevlerini işler. Tüm hesaplamalar tamamlandığında, tüm taraflardaki veri güncellemesi mevcut veri parçaları ve kalan P-1 kısmi veri parçaları tarafından tamamlanabilir. Bu şekilde, GraphChi, grafikteki tüm köşe programlarının hesaplamasını tek seferde tamamlamak için P veri dilimlerini artan köşe kimliklerine göre işler; bu genellikle makine öğrenimi algoritmasının bir yinelemesidir. Bu nedenle, P2 disk okuma işlemlerinde ve P2 disk yazma işlemlerinde herhangi bir yineleme tamamlanmalıdır. Yukarıdaki işlemde köşe programının hesaplanması, kesinlikle köşe kimliğine göre küçükten büyüğe doğru gerçekleştirilir, çünkü ilk olarak tüm köşe aralığı artan köşe kimliğine göre numaralandırılır. Bir köşe aralığında, farklı alt grafiklerin hesaplama görevleri aynı anda birden fazla iş parçacığında işlense de, GraphChi önceden bu tür köşelerin olup olmadığını kontrol edecektir. Bunların gelen kenarları aynı zamanda aralıktaki bir tepe noktasının giden kenarlarıdır. Bu kenarlar Bir çatışma oluşturun. GraphChi, çakışan kenarları olan noktaların önce yürütülmesine izin verir, böylece tüm süreç belirleyici serileştirilebilir işlemleri garanti edebilir. Buna karşılık, programın paralel işlemesinin doğruluğu sağlanır.
Dağıtılmış bilgi işlem sistemleri (GraphX, Giraph, Pregel ve GraphLab gibi) 1 milyar köşe ölçekli grafik verisini işleyebilir, ancak bu çözümler aynı zamanda önemli sayıda kullanıcı için çok pahalı olan büyük ölçekli bilgisayar kümeleri gerektirir. Aynı zamanda, disk tabanlı bağımsız grafik hesaplama sistemleri (GraphChi, X-Stream gibi) ucuz ve rekabetçi işlem yetenekleri sağlar. Örneğin, PageRank algoritmasını 1,5 milyar kenarlı bir Twitter sosyal ağında çalıştırmak için Spark 50 bilgisayar (100 CPU) ve 8.1 dakika gerektirirken, GraphChi yalnızca 1 MacMini ve 13 dakika gerektirir. Huawei Noah tarafından bağımsız olarak geliştirilen grafik hesaplama sistemi VENUS, yalnızca sıradan bir PC ve 5 dakika gerektirir.
Noah diyagram bilgi işlem sistemi VENUS
2013'ten bu yana, Huawei'nin Noah's Ark Laboratuvarı grafik hesaplama sistemlerinin, grafik madenciliği algoritmalarının ve ticari uygulamaların geliştirilmesinden sorumlu büyük ölçekli grafik veri madenciliği araştırma projeleri başlattı. Akademik olarak proje çeşitli araştırma sonuçları üretti ve belirli teknolojik atılımlar gerçekleştirdi; ticari olarak Huaweinin işinde önemli uygulamalar elde etti. Bunların arasında, gelişmiş grafik hesaplama sistemi VENUS, çeşitli büyük ölçekli grafik veri madenciliği uygulamalarını verimli bir şekilde destekleyebilen, endüstrideki en hızlı tek bilgisayarlı grafik hesaplama platformlarından biri haline geldi. Şu anda VENUS sistemi, Huawei mobil uygulama pazarında 1 milyar kullanıcı günlüğü verisini analiz ederek reklam ve mobil uygulama öneri hizmetleri için önemli hedef müşteri seçimini destekliyor.
Şekil 2 VENUS mimarisi
Şu anda grafik hesaplamanın karşılaştığı ana zorluklar, bağımsız sistemin yüksek disk GÇ'sine sahip olması ve büyük belleği etkin bir şekilde kullanamamasıdır; dağıtılmış sistemin zor grafik bölümleme sorununu çözmesi gerekir ve hesaplama süreci yüksek ağ yükü üretecektir. GraphLab, sistemin genel genişletme performansı için bir darboğaz olarak, düğüm eklerken işlem süresini bile artırabilir. Bu zorlukların üstesinden gelmek için, VENUS grafik hesaplama sistemi ilk tasarımından itibaren yeni bir genişleme modunu düşündü: dikey genişleme + yatay genişleme. Özellikle, önce verileri ölçeklendirmeden, önce tek bir hesaplama düğümünün grafik hesaplama sistemini ölçeklendirme yeteneğine tam anlamıyla izin verin ve ardından büyük ölçekli bir bilgi işlem kümesinde birden çok düğüme ölçekleyin Homojen hesaplama. Büyük miktarda hesaplama ve yüksek karmaşıklığa sahip grafik algoritmalarıyla uğraşmak.
Disk tabanlı ardışık düzen hesaplama modeli
VENUS tarafından önerilen köşe merkezli boru hatlı grafik hesaplama modeli, disk tabanlı grafik IO'yu önemli ölçüde azaltarak sistemin belirgin IO darboğazını büyük ölçüde iyileştirir. Hadoop ve Spark gibi yaygın büyük veri platformlarına göre, VENUS'un tasarım konsepti, büyük miktarda veri için gereken büyük miktarda IO ile başa çıkmak için verileri ölçeklendirmek ve büyük ölçekli kümelerde eşzamanlı olarak büyük verileri okumaktır. VENUS, hiyerarşik depolamaya dayalı köşe merkezli boru hatlı grafik hesaplama modeli olarak adlandırılan harici bellek algoritmalarına dayanan benzersiz bir teknik yaklaşıma sahiptir.Tek bir makinede grafik hesaplama sisteminin ölçeklenebilirliğini aşmış ve disk bant genişliğinin nasıl etkili bir şekilde kullanılacağını ve grafiklerin nasıl azaltılacağını çözmüştür. Hesaplamada büyük grafik verilerine erişmenin IO problemi.
Disk tabanlı bağımsız bir grafik hesaplama sistemi olan GraphChi'de, bir grafik birden çok veri parçasına bölünür ve her veri parçasının bellekte depolanması garanti edilir. Her veri parçası, sürekli bir köşe aralığı ve bu köşelerin iç ve dış kenarları dahil olmak üzere eksiksiz bir alt grafik içerir. Grafik hesaplama birden çok yinelemeden oluşur ve her yineleme için sistem, her bir köşede kullanıcı tanımlı bir güncelleme işlevi yürütür. Her yinelemede, sistem her veri dilimini sırayla işler ve güncelleme işlevini her veri diliminde paralel olarak yürütür. Bir veri dilimini işlerken, 3 adıma bölünür: ilk adım yüklemek (Yükle), yani veri dilimini diskten okumak; ikinci adım, güncellemektir (Güncelle), yani veri diliminin karşılık gelen alt dilimi Güncelleme işlevi grafik üzerinde yürütülür; son adım, güncellenen alt grafiği sabit diske geri yazacak olan Yazmadır. GraphChi sisteminde, her bir veri dilimini işlemeden önce, tüm veri diliminin belleğe bir bütün olarak aynı anda yüklenmesi gerekir, bu da grafik hesaplama ve IO'nun paralel olarak tamamlanamamasıyla sonuçlanarak işlem hızını düşürür. Ek olarak, geri yazma aşamasında, sistemin mevcut alt grafikteki kenarların güncellemesini diğer veri dilimlerine yayması gerekir, bu da çok sayıda rastgele IO üretecektir.
Başka bir disk tabanlı grafik hesaplama sistemi olan X-Stream, kenar merkezli bir grafik hesaplama modeli önerir. Bu modelde, kullanıcının iki güncelleme işlevi (dağıtma ve toplama) tanımlaması gerekir ve bu iki işlev, köşeler yerine kenarlarda yürütülür. Her yineleme 3 adıma bölünmüştür: ilk adım yayınlamaktır (dağıtmaktır): sistem tüm kenarları sırayla tarar ve her kenar için bir güncelleme mesajı oluşturmak için dağılım işlevini kullanır; ikinci adım karıştırmaktır: sistem sırası Tüm güncelleme mesajlarını tarayın ve mesajları, güncelleme mesajının hedef tepe noktasına göre karşılık gelen veri diliminin mesaj ara belleğine koyun; son adım toplamak (toplamaktır): sistem, her bir veri diliminin güncelleme mesajını sıralı olarak tarar ve güncelleme için toplama işlevini uygular Hedef tepe noktası. Dağılım ve toplama işlevlerinin yürütülmesi yalnızca o anda taranan kenara veya güncelleme mesajına bağlı olduğundan ve ilgili alt grafiğin bilgisine bağlı olmadığından, X-Stream ardışık düzenlenmiş işleme modu elde etmek için sıralı IO tarama kenarlarını ve güncelleme mesajlarını kullanabilir. Sistem, okuma işlemi ve hesaplamaya paralel olabilir. Ancak, X-Stream'in ara sonuçları (yani güncelleme mesajları) sabit diske geri yazması gerekir, bu da sıralı IO'yu ikiye katlar ve ek hesaplama ve veri yükleme ek yükü oluşturur. Ek olarak, kenar merkezli grafik hesaplama modeli önceki köşe yönelimli modelden farklı olduğu için, çok sayıda mevcut genel köşe merkezli grafik hesaplama algoritmaları ödünç alınamaz. Dahası, kullanıcıların X-Stream üzerinde grafik algoritmaları uygulamak için yeni bir soyut grafik hesaplama yöntemi kullanmaları gerekiyor, bu da zorluğu artıracak. Ek olarak, bazı önemli grafik algoritmalarının (topluluk keşif algoritmaları gibi) X-Stream üzerinde uygulanması zordur.
VENUS sistemi ayrıca grafik hesaplama için yeni bir veri dilimleme yöntemi ve yeni bir harici bellek modeli kullanır. Bu sistemde, her veri parçası iki bölüme ayrılmıştır: v-shard ve g-shard: v-shard, tek bir parçadaki köşe verileridir, veri miktarı azdır ve sık sık değiştirilmesi gerekir; g-shard Kırıktaki grafiğin yapısı, büyük miktarda veriye sahip olan ve değiştirilmeyecek olan kenar verileridir. VENUS daha sonra yeni veri parçalarının grafik hesaplaması için yeni bir harici bellek modeli yaratır: grafik hesaplama yürütme sırasında, sistem tüm g-parçalarını taramak için sıralı disk IO kullanır ve disk taramalarından belleğe sürekli olarak g-shard disk bloklarını okur. , Ve s-parçasının yürütülmesi için gerekli olan belirli bir v-parçası her zaman bellekte saklanır. Yukarıdaki şekilde gösterildiği gibi, g-shard'daki karşılık gelen tüm güncelleme fonksiyonlarını işlerken, gerekli tüm köşe verileri, doğrudan erişim için bellekte karşılık gelen v-shard içindedir. G-shard'ın disk bloğu tarafından okunduğunu ve belleğe daha fazla v-shard verisinin girebilmesini sağlamak için hemen hesaplanıp bellekten atıldığını unutmayın. Bu şekilde VENUS, tüm grafik kenarının verilerini (g-shard) okumak için daha hızlı sıralı erişim IO bant genişliğini kullanabilir ve sistem ayrıca verileri okurken zaman içinde hesaplamalar gerçekleştirebilir ve sistemin genel çalışma süresini kısaltır.
Bir g-shard disk bloğu diskten her tarandığında, sistem ilk olarak, farklı v'nin tüm bitişik kenarlarının g-shard disk bloğundan çıkarılmasını içeren, farklı köşelere v ait çok sayıda bitişik Gv alt grafiği elde eder ve v-shard, tüm bitişik köşelerin değerlerini okur. Ardından, farklı alt grafik parçalarına dayalı analiz ve hesaplama çalıştırmak için her bir iş parçacığı bitişik bir alt grafiği işleyen birden çok farklı iş parçacığı kullanın. Bir dizi yeni tepe noktasının değerlerini hesaplayın ve bunları bellekteki v-parçasına güncelleyin. Bir sonraki g-parçaları ve v-parçaları grubu işlenene kadar buna basmaya devam edin.Tüm g-parçaları ve v-parçaları işlendiğinde yineleme sona erer. Genel olarak, grafik hesaplama modelinin kenarlarının ve tüm köşelerinin değerlerini ayrı ayrı depolamak için disk tabanlı v-shard ve g-shard kullanmak, kenarlara göre depolandığında mevcut grafik hesaplamalarındaki tüm köşelerin değerlerinin birden çok kopyasına olan ihtiyacı ortadan kaldırır. Güncellemeleri senkronize etme ihtiyacının neden olduğu ek disk erişimi yükü, mevcut disk tabanlı grafik hesaplamasındaki toplam okuma ve yazma miktarını büyük ölçüde azaltır. Şekil 3'te gösterildiği gibi, mevcut disk grafik bilgi işlem sistemleri GraphChi ve Xstream ile karşılaştırıldığında VENUS, grafik hesaplamada okunan ve yazılan toplam disk verisi miktarını önemli ölçüde azaltır: 41 milyon köşeli ve 1,4 milyar kenarlı bir Twitter grafiğini işlerken (8GB RAM), VENUS, sırasıyla GraphChi ve Xstream'in diske yazılan toplam verisinden 40 ve 50 kat daha küçüktür.
Şekil 3 Mevcut sistemlerle karşılaştırıldığında, VENUS diskleri okumak ve yazmak için daha az maliyetlidir
Bu akademik fikir için, üst düzey bir veri yönetimi konferansı olan ICDE2015'in jüri üyeleri şunları söyledi: "Önerilen teknikler, çoğunlukla sıralı bir G / Ç modelini korurken diske yazılan veri miktarını büyük ölçüde azaltacak şekilde köşe merkezli işlemeyi kolaylaştırır. çok pratik ve güncel bir konu hakkında önemli bir araştırma. " Bağımsız sistemde VENUS performansı, GraphChi ve X-Stream'den daha iyidir ve işlem süresi genellikle 3 ila 10 kat daha hızlıdır; dağıtılmış sistemlerle karşılaştırıldığında, VENUS tek başına Spark kümesine yakın bir etkiye ulaşabilir (50 ünite, 100 CPU). Huawei içindeki belirli bir iş senaryosunun gereksinimlerine yanıt olarak, VENUS büyük resimde 200 milyar bağlantıyı başarıyla işledi (bir yineleme 81772.1 saniye sürüyor).
Ek olarak, Huawei mobil uygulama pazarındaki görevlerin analizinde, bağımsız grafik hesaplamanın üretim sistemlerini dağıtırken ek bir avantaja sahip olduğunu da bulduk: günlük olarak güncellenen büyük miktarda günlük verisinin analizi nedeniyle, hesaplamanın genellikle geceleri birkaç saat içinde tamamlanması gerekir. Bilgi işlem ortamında, çok sayıda görev genellikle geceleri önceden planlanır ve bu da bilgi işlem kaynaklarının azalmasına neden olur. Mevcut grafik hesaplama sistemi, büyük grafikleri işlerken tam grafiği belleğe yüklediğinden, daha fazla sunucuya ihtiyaç duyulur ve bu da grafik hesaplama görevlerini yürütmek için daha yüksek koşullar belirler ve bu da uygulaması zordur. Örneğin, ClueWeb işlenirken, her sunucu 380G bellek ile yapılandırılır, Spark en az 10 sunucu gerektirir ve GraphLab işlemek için en az daha fazla sunucu gerektirir. Bu durumda, VENUS, bağımsız işlemenin avantajlarından tam anlamıyla yararlanarak, daha kolay konuşlandırılabilir ve kullanılabilir.
Şekil 4 VENUS vs Spark: Twitter'da PageRank (41M köşe, 1,4B kenar)
Şekil 5 VENUS vs GraphChi: ipucu ağında PageRank (1B tepe noktası, 43B kenarı)
Trend Görünümü
Disk tabanlı tek makineli grafik hesaplaması yukarıdaki avantajların çoğuna sahip olsa da, büyük grafik verilerinin tek bir bilgisayarda okunması ve yazılması hala büyük bir darboğazdır.Örneğin, ClueWeb'i okumak için geleneksel diskleri kullanmak bir keresinde yaklaşık iki saat. Gelecekte, dağıtılmış dosya sistemi HDFS'ye dayalı disk hesaplamanın büyük bir potansiyele sahip olduğu düşünüldüğünde, ilgili dağıtılmış bir grafik hesaplama modelinin nasıl tasarlanacağı hala daha zordur ve ilgili araştırmalar kademeli olarak yürütülmektedir. Ek olarak, mevcut uygulamalar, bir dizi grafik sisteminin aynı anda çevrimdışı grafik hesaplamasına sahip olabileceğini ve çevrimiçi grafik veritabanı sorgusunun çok değerli olduğunu, ancak bu, grafik veritabanı depolama modunun nasıl tasarlanacağına yönelik daha büyük zorluklar getirdiğini, bir ön girişim olduğunu göstermektedir.
Dağıtılmış bir grafik hesaplama sisteminde, grafik kümedeki hesaplama düğümlerinin sayısına göre eşit parçalara bölündüğünden, ana bilgisayarların, genel hesaplamayı ilerletmek için belleklerindeki bilgi işlem durumunu birbirlerine söylemek için sürekli olarak birbirleriyle iletişim kurması gerekir. Bu şekilde, alt grafiğin kalitesi, hesaplama işlemi sırasında üretilen ağ mesajlarını doğrudan etkiler ve çok sayıda ağ mesajı, grafik hesaplamasının genel performansını büyük ölçüde azaltacaktır. Raporlara göre, bellek hesaplama için mevcut dağıtılmış grafik hesaplama sistemi, mesaj göndermek ve almak için zamanın% 50'sinden fazlasını alıyor. Bununla birlikte, minimum maliyetli tek tip çok parçalı grafik problemi zor bir NP problemidir ve polinom zamanında verimli bir çözüm elde edilemez. Bu nedenle, büyük miktarda bellek ve ağ kullanımını azaltmak için dağıtılmış grafik hesaplama sisteminin nasıl genişletileceği, gelecekte dağıtılmış grafik hesaplama alanında çözülmesi gereken bir eğilim problemidir.
Dağıtılmış bir hesaplama ortamında, her ana bilgisayar, yerel diskteki grafik verilerini tam olarak barındırmak için nispeten yeterli disk alanına sahip olduğundan, VENUS, grafik hesaplama sisteminin yeteneğini tek bir düğümde çoğaltarak dağıtılabilir ve genişletilebilir. Avantajı şudur: hesaplama işlemi sırasında, sistemin hesaplama için bu sefer sadece az miktarda hızlı sıralı disk IO ile depolanan grafik verilerini okuması gerekir ve farklı ana bilgisayarlar arasında grafik verilerinin ağ iletişimini gerektirmez. Dahası, bu tür dağıtılmış grafik hesaplama, aynı anda birden fazla düğümde aynı grafik üzerinde homojen hesaplama gerçekleştirebilir, çünkü aynı düğümdeki aynı hesaplama grubu, aynı grafik verilerini paylaşır.IO planlama ek yükünü paylaşır ve çok çekirdekli CPU, FGPA'dan tam olarak yararlanabilir. Pratik uygulamalarda zaman verimliliği talebini karşılamak için donanımın büyük ölçekte birden fazla köşe programını paralel olarak yürütmesini bekleyin.
Önce verileri ölçeklendirmeyelim, önce tek bir hesaplama düğümünün grafik hesaplama sistemini büyütme becerisine tam anlamıyla izin verelim ve ardından birden çok düğümde homojen hesaplamayı ölçeklendirmek için büyük ölçekli bir hesaplama kümesine gidelim , Grafik algoritması ile büyük miktarda hesaplama ve yüksek karmaşıklık ile başa çıkmak için. Örneğin, büyük ölçekli grafikler için SimRank algoritmasını ele aldığımızda, daha pratik bir çözüm, yani rastgele yürüyüşe dayalı Monte-Carlo kullanıyoruz. Bu şemadaki temel bilgi işlem görevlerinden biri şudur: Grafikteki N düğümleri için, her düğümden kaynak noktası olarak düğümle bağımsız olarak rastgele bir yürüyüş yolu aramamız gerekir. SimRank algoritmasını doğrudan uygulayan mevcut grafik hesaplama sistemi perspektifinden, rastgele yürüyüşe dayalı Monte-Carlo algoritması, aynı grafiğin N kez hesaplanmasını gerektirir. Her rastgele yürüyüş, grafikteki her farklı başlangıç düğümünden başlar ve her adım, ileriye gitmek için geçerli düğümün bitişik bir tepe noktasını rasgele seçer. Bu işlemi uygulamak için mevcut grafik hesaplama sistemi kullanıldığında, hem GraphLab hem de GraphChi, belirli bir başlangıç düğümünden rastgele bir yürüyüşü doğrudan uygulayabilir. Bunlar arasında, bir sonraki bitişik köşeye rastgele yürüyüşün her adımı, mevcut grafik hesaplamasının bir yinelemesini gerektirir ve ardından yürüyüş yolunun ne kadar süreyle örneklenmesi gerektiğini, sistem örneklemeyi tamamlamak için kaç tane yineleme işler. Bu nedenle, mevcut kıyaslama dağıtılmış grafik hesaplama sistemi GraphLab'ın bu algoritmayı uygulamasının en doğrudan yolu, N örnek için N grafik hesaplaması çalıştırmaktır ve her grafik hesaplaması bir örnekleme hesaplamasına karşılık gelir. Hesaplama süresi, dağıtılmış bir örneklemenin hesaplama süresinin N katıdır.
Buna karşılık, VENUS, grafiği tek bir düğümde kopyalayarak bu N örneği aynı anda birden çok farklı ana bilgisayarda çalıştırabilir. Şu anda, bilgi işlem kümesindeki her ana bilgisayar tam haritayı görebilir, çünkü yerel diskteki harita verilerini tam olarak barındırmak için nispeten yeterli disk alanımız vardır. Bu şekilde, aynı zamanda bölünmeyi de önleyerek bu çetrefilli sorunu çözebilirsiniz. Homolog olmayan rastgele yürüyüşler birbirinden bağımsızdır ve farklı ana bilgisayarlar arasında ağ iletişimi olmadan her ana bilgisayarda aynı anda ayrı ayrı hesaplanabilir. Bu, ölçeklendirdiğimiz birden çok düğümde homojen rastgele yürüdüğünde örnekleme hesaplamasına eşdeğerdir. N örnek, bu birden çok farklı ana bilgisayarda aynı anda çalıştırılır, böylece toplam süre, tek bir örneğin hesaplama süresinin N / M katıdır, burada M ana bilgisayar sayısıdır. Bu yöntemin daha iyi ölçeklenebilirliğe sahip olduğu görülmektedir.
Yazar hakkında:
Cheng Jiefeng, Huawei'in Nuh'un Gemisi Laboratuvarı'nda araştırmacıdır. Çalışma, büyük ölçekli dev grafiklerin çevrimiçi aramasına, çevrimdışı analiz ve madencilik algoritmalarına ve ölçeklenebilir grafik madenciliği sistemlerine odaklanıyor ve JVLDB, TKDE, KDD, VLDB ve ICDE gibi 30'dan fazla akademik makale yayınladı.
Liu Qin, Huawei'nin Nuh'un Gemisi Laboratuvarı'nda araştırmacıdır. Ana araştırma yönleri sistem yazılımı, paralel ve dağıtılmış sistemlerdir. VLDB, ICDE, DSN, CIKM ve TKDE gibi uluslararası üne sahip konferans dergilerinde birçok akademik makale yayınladı.
Li Zhenguo, Huawei's Noah's Ark Laboratory'de Grafik Madenciliği Teknolojisi Başkanı, Doktora Sonrası Araştırmacı, Columbia Üniversitesi Elektronik Mühendisliği Bölümü Araştırma alanları arasında yapay zeka ve makine öğrenimi yer alıyor ve NIPS, ICML, CVPR, ICCV, VLDB ve diğer ilgili konferanslarda birçok akademik makale yayınladı.
