genel bakış

Birkaç ay önce Metal'de bir ilişkisel veri tabanı prototipi üzerinde çalışmaya başladım. Apple, M1 Max ve M1 Ultra'yı birkaç ay önce 128 GB'a varan birleşik bellekle (Mac Studio'da) piyasaya sürmüştü.

Bunu, çok fazla GPU belleği gerektiren çok ağır işlemlerle bir şey yapmak için bir fırsat olarak gördüm: bir GPU'da büyük ilişkisel tabloları işlemek.

Bir GPU'da ilişkisel bir veritabanı yazmayı düşünen ilk kişi ben değildim. Rapids.AI üzerinde oluşturulmuş bir GPU ilişkisel veritabanı olan BlazingSQL gibi veritabanları . Rapids.AI, Pandalar gibi birçok popüler Python kitaplığının işlevselliğini yansıtan ancak GPU'da eşdeğer işlevleri çalıştıran bir NVIDIA Python kitaplığıdır. NVIDIA, veri merkezine yoğun bir şekilde yatırım yapıyor ve özellikle makine öğrenimi ve büyük veri işleme için kartlarında çalışan daha fazla araç geliştirmeye yardımcı oluyor.

Son zamanlarda Apple konferanslarını izlerken, gerçekten kullanılmayan pek çok potansiyel performans olduğunu hissettim. Gördüğüm kadarıyla, geliştiriciler yeni çiplerin yeni grafik özelliklerinden yararlanıyor. Bilgi işlem tarafında, Metal ile oluşturulmuş demolar ve açık kaynaklı yazılımlar eksikti. Apple bir parçacık simülasyonunun örnek bir projesini yaptı, sanırım CUDA örneğinin eşdeğerini gösteriyor. Arada CPU'ya geri dönmek zorunda kalmadan GPU'da CUDA'da hesaplamayı ve OpenGL'de işlemeyi nasıl kullanabileceğinizi gösterirler. Apple'ın GPU'yu yoğun bir şekilde kullandığı diğer yer, AI görevleri içindir. Neural Engine bir modeldeki bir işlemi desteklemediğinde, CoreML daha fazla performans için otomatik olarak GPU'ya geri döner. Bu çok yararlı ve büyüleyici olsa da,

Veritabanlarını gerçekten sevdiğim için ilişkisel bir veritabanı seçtim ve onlar için birkaç tasarım düşündüm, bunlardan bazılarının prototiplerini yıllar boyunca yaptım. İlişkisel veritabanları da dizgeler ve boş değerler kullandıkları için ilgi çekicidir. Hem AI örneği hem de parçacık simülatörü, çok etkileyici olmakla birlikte, yalnızca kayan nokta ve tamsayıları kullanır.

Oluşturduğum uygulama burada bulunabilir: MetalDB Github

Tasarım fikirleri

Sürecin tam başında mı yoksa ortasında mı olduğunu hatırlamıyorum, ancak sorgu yürütme planını oluşturan sorgu aşamalarının grafiğinden bahseden BigQuery Query Plans belgelerinden ilham aldım.

Metal ile ilgili en önemli tasarım sınırlamalarından biri, derleme zamanında tüm belleğin statik olarak boyutlandırılması gerekmesidir. Bir veritabanı satırında kaç tane dize olduğunu veya derleme zamanında her bir dizenin ne kadar uzun olacağını bilmediğim için bir diziyi kopyalayamadığım için bu zorluklar ortaya çıkardı.

Tüm verileri GPU'dan CPU'ya verimli bir şekilde geri kopyalamak için bir önek toplamı algoritması kullanmanın, her bir iş parçacığı bir satır işliyorsa en basit olacağını düşündüm. Ayrıca Metal'de bir ThreadGroup olan mevcut en büyük senkronize edilebilir bloğu kullanmam gerekiyordu.

Kısmen bir optimizasyon ve kısmen de kişisel bir meydan okuma olarak, GPU üzerinde yapılan iş miktarını en üst düzeye çıkarmak istedim. Bu nedenlerden dolayı, CPU'da CSV dosyalarını okumaya ve GPU'da CSV ayrıştırmasını yapmaya karar verdim.

Uygulama sırasında, bir hata ayıklayıcıda birim testlerinin adım adım gerçekleştirilebilmesi için veritabanını CPU üzerinde test edebilmek istedim. Bu nedenle, tüm Metal çekirdeklerimin başlıklar olarak yazılması için derleme boru hattını kurdum. Sonuç olarak, onları Metal çekirdek dosyalarına dahil edebilirim, ancak C++'daki testlere de dahil edebilirim. Bu tasarım ayrıca Metal başlıklarında sabitleri ve türleri tanımlamama ve onu çağıran C++ kodunda her zaman aynı olmalarını garanti etmeme izin verirdi.

Diş Grupları ve Metal kavramları hakkında arka plan

Daha fazla fikir ve açıklama için arka plan olarak, Metal uygulama ızgaralar halinde düzenlenmiştir. Izgara, 1B, 2B veya 3B ThreadGroups grubudur. Bir ThreadGroup, bu ızgara içinde senkronize edilebilir bir gruptur. Bir ThreadGroup içindeki iş parçacıkları, çözgü adı verilen başka gruplara bölünür ve yürütülür.

Bir iş parçacığı, GPU programlamadaki en temel bloktur ve kabaca bir CPU çekirdeğindeki iş parçacığı modeline dönüşür. Talimatların tek, doğrusal, sıralı bir şekilde yürütülmesidir. İş parçacığının doğrudan erişebileceği ve paylaşılan belleğe okuma ve yazma yapabileceği kayıtları vardır. CPU'dakinden farklı bir bellek modelidir, ancak bu, bu makalenin kapsamı dışındadır.

Bir çözgü (Metal belgelerinde SIMD olarak adlandırılır) genellikle 16 veya 32 iplikten oluşan bir gruptur. Potansiyel olarak farklı veriler (SIMD, Tek Yönerge, Çoklu Veri) üzerinde olmasına rağmen, aynı komut bir çözgü içindeki tüm iş parçacıklarında aynı anda yürütülmelidir. Eğer thread'lerden bazıları kodda farklı bir yol izliyorsa, o çözgü içindeki tüm thread'ler tüm dalların seri olarak çalışmasını beklemelidir. Bu, mümkün olduğu kadar az dallı GPU kodu tasarlamaya yol açar, öyle ki bir çözgü içindeki tüm iş parçacıklarını mümkün olduğunca meşgul tutabilirsiniz.

CUDA ve OpenCL gibi diğer sistemler benzer kavramlara sahiptir, sadece farklı isimlerle.

uygulama

Uygulama bağlantısı:https://github.com/mattpaletta/metaldb

Bence en mantıklısı verinin sistem üzerinden akış sırasına göre uygulamadan bahsetmek. Bununla birlikte, bu, onu uygulamaya nasıl başladığımın neredeyse mükemmel tersidir.

İkili

Üretilen nihai sonuç çok basittir. Adı verilen bir ikili dosyadır metaldbve içinde sadece bir ana işlevi vardır. Uygulamayı çok hafif hale getirdim, böylece ben ve diğerleri, iç kütüphaneleri gelecekte diğer kütüphanelerin ve uygulamaların bir parçası olarak kolayca yeniden kullanabilirim.

Motor

Motor, sistem mantığının çoğunun koordine edildiği yerdir. Motor QueryPlanner, QueryPlanner kitaplığında uygulanan ile ve Schedulerayrıca oluşturulan sorgu planının yürütülmesini yürütmekten ve koordine etmekten sorumlu olan ile etkileşime girer.

Sorgu Ayrıştırıcı

Sorgu Ayrıştırıcı, SQL benzeri bir sorguyu sistemin geri kalanı tarafından daha kolay ayrıştırılabilen bir AST'ye dönüştürmekten sorumlu olan bileşendir .

Veritabanının bu ilk sürümü, bir Sorgu Ayrıştırıcı uygulamaz. Bunun yerine, test etmek istediğim çeşitli sorgular için AST'yi kodladım. Ayrıştırıcı yazmak ve bir AST üretmek kulağa çok ilginç gelse de başka bir projede yaptığım bir şeydi ve bu projenin odak noktası değildi.

Ayrıca bu projenin üretime hazır bir veritabanı olmasını da düşünmedim. Bu nedenle, şu anda bir sorgu ayrıştırıcısına ihtiyaç duymuyor, ancak tüm taslaklar, eğer istersem daha sonraki bir noktada uygulamak için benim için orada.

Sorgu dizelerini kabul eden sisteme ek olarak, sonunda Pandalara benzer, ancak C++ dilinde bir Dataframe API uygulamayı planlıyorum. Benim bakış açıma göre, bu tür bir API, diğer kitaplıkların birlikte çalışması için daha basit olacaktır. Bu aynı zamanda, diğer kitaplığın yalnızca daha sonra çözümleyici tarafından hemen yeniden ayrıştırılması için bir sorgu dizesi üretme adımını da kaydeder. Bu Dataframe API'si de gelecekteki bir çalışma olarak bırakılmıştır.

Bir test veri seti olarak ilk olarak halka açık olan Iris veri setini kullandım . Bu veri kümesini seçtim çünkü nispeten küçük, CSV biçiminde ve çoğunlukla boş değerler içermeyen sayılar.

Bu veri setini çalıştırdıktan sonra, birden çok dosya içeren çok daha büyük bir veri setini denemek istedim. Bunun için New York Taxi Dataset'i kullandım . Bu daha büyük veri seti, beklemediğim bazı ilginç zorlukları kanıtladı, daha sonra bunun hakkında daha fazla bilgi vereceğim.

Sorgu Planlayıcı

Sorgu Ayrıştırıcı AST'yi oluşturduktan sonra, sonraki bileşen Sorgu Planlayıcı'dır. Bu, AST'yi optimize edilmiş bir yürütme planına dönüştürmekten sorumludur.

Optimize edilmiş bir yürütme planı yapmanın ilk adımı, bir plan yapmaktır. BigQuery referansından esinlenerek , bir yürütme planını "Aşamalar" grafiğine bölme fikrini beğendim. BigQuery'de her aşama bir veya daha fazla adımdan oluşur. Her adım bir okuma veya yazma, toplama veya birleştirme vb. olabilir. Adımların ayrıntı düzeyine inmek istemedim, ancak benzer bir konseptim var, ben "kısmi" diyorum.

Bir AST'den bir aşama grafiğine geçmek için, önce tablo(lar) için diskteki dosyaları listeliyorum. Sonra AST'nin yapraklarına gidiyorum ve her biri için o dosyayı okuyacak yeni bir aşama oluşturuyorum.

Ağaca geri dönerken, mevcut sahnenin bir parçası olarak yeni bir bölüm mü yoksa yeni bir sahne mi oluşturacağıma karar veriyorum. Kilit nokta, bir adım için GPU'dan CPU'ya veya tam tersine gitmem gerektiğinde, yeni bir aşama oluşturuyorum. Bu, CPU ile GPU arasındaki aktarım sürelerini en aza indirirken GPU'da mümkün olduğunca çok verinin işlenebileceği anlamına gelir. Bu, özellikle birleşik belleğe sahip olmayan cihazlar için geçerlidir.

Her aşamada çalıştırılacak tekil bir kısmi liste vardır. Zamanlayıcı ile ilgili bölümde daha fazlasını keşfedeceğimiz için, bunlar daha sonra bu aşamada GPU'ya talimatlar olarak çevrilecektir.

Her yeni aşama oluşturduğumda, GPU'ya bilgileri CPU'ya geri kopyalamasını söyleyen bir "Karıştırma Talimatı" ekliyorum.

Gelecekte, her dosyadan okunan ve okunduktan sonra CPU'ya geri kopyalanan veri miktarını en aza indirmek için sorguları yeniden yazabilen bir optimize edici de yazacaktım.

zamanlayıcı

Zamanlayıcı, sorgunun paralel yürütülmesinden sorumludur. Bunu yapmak için kendi çok iş parçacıklı kitaplığımı yazmak istedim. Uygulamamı , açık kaynaklı bir C++ görev grafiği kitaplığı olan TaskFlow üzerine yazdım.

Üst düzeyde, görev grafiğinin oluşturulması aşamaların grafiğini takip eder. Her aşama grafikte bir görevdir ve çocuklarına bağlıdır.

Bir aşama içinde, CPU veya GPU'da yapılacak adımların her bir kısmı, listesi sırayla genişletilir. Her kısmi kaydedilirken, görev grafiği içinde bağlanabileceği birkaç görevi vardır.

Bağlanabilecek ana görev, önceki görevin kodlama görevidir. Kısmi, üst kısmi kodlama görevine bağlı yeni bir görev oluşturmalıdır. Kendisini GPU'ya gönderilebilen seri hale getirilmiş bir temsile kodlamak için iletilen Kodlayıcıyı kullanır. Çoğu görev için gerekli olan tek şey budur ve kısminin uygulanması Metal'deki GPU'dadır.

Kullanılabilir diğer görev, iş görevidir. Bu, bir kısminin, varsayılan davranış yerine o kısmi için işin nasıl yürütüldüğüyle ilgili bir şeyi geçersiz kılmak istemesi durumunda mevcuttur.

Çoğu görev, arabellekleri bir veya daha fazla alt aşamadan okur ve çıktı arabelleğine yazar. Okuma yönergesi benzersizdir çünkü alt arabelleklerden değil diskten okuması gerekir.

Okuma talimatı, atandığı CSV dosyasını (şu anda uygulanan tek dosya türü) okuyan ve onu bir arabelleğe okuyan bir görevler zinciri kurar. Bir ara belleğe okuma yaparken, geçerli satırın kaymasını takip eder ve bunları RawTableaşağıda açıklanan nesnenin bir parçası olarak saklar.

Dosya okunduktan sonra, GPU satırları işlemeye başlamak için serbesttir. Veritabanının tasarımı, satır başına bir iş parçacığı gerektirir. Metal'in, ThreadGroup başına atanabilecek iş parçacığı sayısıyla ilgili bir sınırı vardır. Bu nedenle önce satırları, her biri bağımsız olarak GPU'ya gönderilecek olan çoklu arabelleklere ayırdık.

TaskFlow, bir görev içinde dinamik alt görevlere izin verir. 'yi aldığımda RawTable, Metal'in programlamama ve orijinal satırları o boyuttaki parçalara ayırmama izin verdiği iş parçacığı sayısını sorguluyorum.

Her yığın daha sonra paralel olarak GPU'ya gönderilir.

Tüm parçaların her biri işlendikten sonra, tüm OutputRownesneleri GPU'dan kopyalayan ve bunları tek bir devde birleştiren bir birleştirme görevi yürütüyorum OutputRow, böylece bir sonraki aşama bunları birlikte okuyabilir.

Gelecekte, birden çok partinin bölünmesini optimize etmek istiyorum. Toplu iş bölünür bölünmez GPU'ya gönderilebilir. Bu yığın geri gelir gelmez, diğer görevler eşzamansız olarak işlenirken son ara belleğe kopyalanabilir.

RawTableEk olarak, tüm satırlar, her biri bir kopyayı saklayan parçalara bölündükten sonra orijinali serbest bırakmak istiyorum . Ek olarak, son arabelleğe kopyalanır kopyalanmaz çıktı arabelleğini yığından serbest bırakabilmeliyim, bu da gereken toplam bellek miktarını azaltmalıdır.

ParseRow Talimatı

Basit ParseRowInstructionbir öncül ile başlar. Her satırın başlangıcı için bir dizin listesi ve satır sayısı ve sütun türleri hakkında bilgi verildiğinde, belirli bir satırın değerlerini ayrıştırın, doğru türlerine dönüştürün.

En basit sütun türü bir dizedir. N satırı için, dosyayı diskten okurken CPU'nun depoladığı dizinine bakarak o satırın başına atlayabiliriz. Daha sonra bu dizine bir işaretçi alabiliriz. Bu sıranın başlangıcı. Herhangi bir sütunun sonu, her seferinde bir karakter ileri gittiğimizde sonraki virgülden (sonraki sütunu işaretleyerek) önceki konumdur veya sonraki satırın başlangıcından bir önceki (satırın son sütunuysa) veya bir arabelleğin sonundan önce (son satırın son sütunuysa).

Talimat, önce her sütunu bir dize olarak okur. Bir sütunu tam olarak açıklandığı gibi ayrıştırır ve onu karakter karakter bir dize olarak okur. Şimdi bir sonraki sütunu okumak için satırın başından başlıyoruz. İlk virgüle geldiğimizde onu başlangıç ​​olarak işaretliyoruz ve ondan sonraki virgüle kadar gidiyoruz. İşlem sonraki sütunlar için tekrarlanır.

Bir tamsayımız varsa, dizgenin başına ve sonuna işaretçileri özel bir stoiişleve iletiriz. Bu, diziyi bir tamsayı gösterimine dönüştüren C standart kitaplığından alınana benzer. Ben de kendi versiyonumu yazdım stof.

Tahmin edebileceğiniz gibi, her seferinde satırın başından itibaren her sütunu okumak çok yavaş ve çok sayıda yinelenen çalışma var. Daha iyisini yapabiliriz, çok daha iyisini.

Sütunun başlangıcını bulmayı optimize etmedeki ilk fark, genellikle az sayıda sütun olmasıdır. Önbelleğe alınacak sütun sayısı olarak 16'yı seçtim.

Bu ilk önbellek düzeyiyle, ilk 16 sütun içindeki bir sütunu okuyorsam, o sütun için önceden önbelleğe alınan işaretçiyi okumaya çalışırım. Boş değilse, zaten değerim var. Satırlar değişmezdir, bu nedenle işaretçi geçerli olmalıdır ve işlem tamamlanır!

İşaretçi boşsa, daha önce önbelleğe alınmış bir sütun bulana veya ilk girişe ulaşana kadar önbelleğim üzerinde 16. sütun dizininden geriye doğru yinelenebilirim.

Durduğum yerden, her seferinde bir karakter olmak üzere saf bir şekilde sırayı yineleyebilirim. Her virgül bulduğumda, sonraki sorguların doğrudan oraya atlayabilmesi için işaretçiyi önbelleğimde o sütunun başına saklarım.

Bu, düz bir işaretçi araması haline geldiğinden, ilk 16 sütuna rastgele erişimin temelde ücretsiz olması gerektiği anlamına gelir. Bu, O(n) olan ilk erişimi hariç tutar .

Peki ya 16'dan fazla sütun içeren satırlar? 15. sütunun nerede olduğunu zaten biliyorum (0'dan başlayarak), bu yüzden doğrudan 15. sütuna atlayabilir ve ardından bundan sonra saf bir şekilde araya girebilirim. 15. sütunun nerede olduğunu bilmiyorsam, hızlı bir şekilde hesaplayabilir ve önbelleğe alabilirim.

Bu oldukça iyi, ancak yapılabilecek bir optimizasyon daha var. Diğer gerçekleştirme, ParseRowInstruction içinde çıktı satırını oluştururken sütunlara sırayla erişmesidir. İlk 16 sütun için sabit boyutlu rasgele önbelleğe ek olarak, erişilen son sütunun başlangıcını ve o sütunun dizinini saklayan ek bir işaretçi tutabiliriz. Bu, ilk önbelleğe alma düzeyinde olduğu gibi sonsuz sayıda işaretçi depolamak zorunda kalmadan, herhangi bir sayıda sütun için sıralı erişimler için düz bir işaretçi aramasına izin verir. Elbette bu iki önbellek katmanı birlikte çalışır. İlk 16 değeri güncellerken last_accessedişaretçiyi de güncelliyoruz.

GPU üzerinde çalışırken, her iş parçacığı tek bir satırdan sorumludur. Yani her iş parçacığının açıklandığı gibi kendi çok katmanlı önbelleği vardır. Önbellek ayrıca hangi satırı önbelleğe aldığımızı da takip eder. Talep edilenden farklıysa, önbelleği sıfırlarız, böylece önbelleğin her zaman ilgili olduğunu biliriz. Bunu, birden çok satırı okuma veya iş parçacıkları arasında önbelleği paylaşma durumlarını kapsayacak şekilde genişletmek mümkündür, ancak bu, ilk uygulamanın kapsamı dışındaydı.

Projeksiyon Talimatı

Karşılaştırıldığında ProjectionInstructionçok basit. Alınması için sütun dizinlerinin bir listesi verilir. Yeni bir TempRow nesnesi oluşturur ve bu sütunları son TempRow'dan kopyalayarak meta verileri yeni TempRow nesnesinde günceller.

Filtre Talimatı

öğesinin temel uygulaması, bir satırı veya FilterInstructiondöndüren bir ifadeye karşı değerlendirmek üzere tasarlanmıştır .truefalse

Bu, yığın tabanlı bir sanal makine olarak uygulandı. Yığın tahsisi derleme zamanında sabitlenir ve bu nedenle her zaman maksimum boyutunu tahsis eder.

Yığının uygulanması biraz ilginçti. VM için bayt kodunu, türleri ve bir türü diğerine aktarma talimatlarını içerecek şekilde tasarlamayı seçtim. Yığın uygulaması heterojen verilere izin verir, ancak türleri sağlamaktan çağıran sorumludur.

Normal bir yığında, bir nesne için kutular oluşturabilirsiniz ve kutu, o şeyin ne tür olduğunu ve o şeyin işaretçisini saklar. Bu durumda, derleyici (henüz uygulanmadı), gerekli tüm dökümü içerecek bayt kodunu yazmaktan sorumludur. Bu, çalışma zamanının yığına xbayt olan bir tamsayıyı itmesine izin verir ve daha sonra bir tamsayı okumaya gittiğinde x, yığından baytları çıkarabilir ve aynı tamsayıyı alabilir. Kutu veya dinamik döküm gerekmez. Bu, tüm türleri doğru hale getirme sorumluluğunu derleyiciye yükler, ancak bu, gelecekteki uygulamaya bırakılır.

Çıkış Komutu

OutputInstructionThreadGroup içindeki ayrı ayrı iş parçacıklarından gelen tüm verileri birleştirmek ve her bir iş parçacığının ihtiyaç duyduğu, ancak gerçekten yalnızca bir kez CPU'ya kopyalanması gereken ve verimli bir şekilde tek bir büyük arabelleğe koyması gereken tüm yinelenen verileri kaldırmak için kullanılır . .

İlk adım, her satırın (her iş parçacığı) kendi boyutunu hesaplamasıdır. Sonra boyutların önek toplamını çalıştırırız. Bu bize verilerimizi yazmaya başlayabileceğimizi bildiğimiz bir indeks verir.

Önek toplamı, GPU hesaplamasında sıklıkla kullanılan bir algoritmadır; burada bir tamsayı dizisi verildiğinde, her i indeksi için i'den küçük tüm öğelerin toplamını içeren yeni bir dizi döndürür . Toplam, i konumu için i öğesini içeriyorsa , buna dahil toplam, aksi halde özel toplam olarak adlandırılır. Uygulamam için özel bir meblağ kullandım.

Veri yazmaya başlamadan önce, iş parçacıklarının OutputRow. Bunun için başlığın yazılmasından sorumlu olan ilk satır başlık boyutunu da kendi boyutuna ekler. Ön ek toplamını yaptıktan sonra, ilk iş parçacığının toplam bayt sayısını başlığa yazabilmesi için satır boyutlarında da bir küçültme çalıştırıyoruz.

Bu tamamlandığında, her satır önek toplamı çıkışından kendi uzaklığına atlayabilir ve baytlarını paralel olarak bu noktadan başlayarak arabelleğe kopyalayabilir ve herhangi bir çarpışma olmayacağı garanti edilir.

TempRow

TempRowMetal'de veriler işlenirken dolaşan veri yapısıdır . İdeal olarak, bellek ayak izini en aza indirmek için öbek üzerinde yeniden boyutlandırılabilir bir öğe ayırırdık TempRow, ancak Metal dinamik bellek ayırmalarını desteklemediği için. Her TempRowsabit boyutta bir arabellektir. 1024 bayt veya 1 kilobayt olarak seçtim. öğesinin ilk bölümü TempRowbir başlıktır, ardından veriler gelir.

Başlıktaki ilk değer uzunluğudur. Bu önemlidir çünkü veriler başlıktan hemen sonra başlar ve başlık, sütun sayısına ve türlerine bağlı olarak değişken bir boyuttadır.

Bir sonraki bayt sütun sayısıdır. Bu sadece 1 bayt olduğundan, maksimum sütun sayısı 256'dır. Çoğu kullanım durumu için bunun yeterli olduğunu düşünüyorum.

Sonraki N bayt, sütun türleridir. Sütunlar şunlardan biri olabilir: Integer, veya Floatbunların Stringnull yapılabilir eşdeğerleri. Bir boole değeri basitçe bir tamsayı olarak ifade edilir.

Bir tamsayı ve bir kayan nokta her zaman sabit bir boyuttadır, bu nedenle, null yapılabilir bir sütun olmadıkça boyutlarını başlıkta saklamamız gerekmez. Aksine, bir dizi herhangi bir sayıda karaktere sahip olabilir. Bu nedenle, tüm değişken uzunluklu sütunların (dizeler ve isteğe bağlı sütunlar) boyutunu sonraki baytlarda saklarız. Yine, bir sütunun boyutu yalnızca 1 bayt olduğundan, bir dizenin maksimum uzunluğu 256 karakterdir.

Başlıktan sonra, sütunların tüm verileri arka arkaya eklenir.

İnşasını daha basit hale getirmek için , arayanın tüm sütun türlerini ve boyutlarını vb. ayrı dizilere yazabileceği TempRowbir yardımcı sınıf vardır . TempRowBuilderDaha TempRowsonra, değerleri kopyalayarak oluşturucudan önemsiz bir şekilde oluşturulabilir.

Sütunlardaki veriler daha sonra sırayla eklenebilir. Dizelerde, tamsayılarda ve değişkenlerde kopyalamaya ve bunları bayt bayt yazmaya yardımcı olacak yardımcı yöntemler vardır.

Bir sonraki yöntem okumaya gittiğinde, TempRowo sütunun arabelleğindeki başlangıç ​​ve bitiş dizinlerini belirlemek için başlıktan okuyan ve baytları uygun türe geri atan yardımcı yöntemler vardır. ColumnTypeArayan, ilgilendiği sütunun türünü o tür olarak okumadan önce sorgulamakla yükümlüdür .

TempRowTüm verileri doğrudan sabit boyutlu bir arabellekten okuduğu için, diğer uygulamalar için bir sınıfa önemsiz bir şekilde uyarlanabilir constexpr.

ÇıktıSatırı

OutputRowtarafından oluşturulur ( OutputRowInstructionyukarıda açıklanmıştır) ve aynı şemayı paylaşan birden fazla satırın taşınması amacına hizmet eder. Tüm tek tek TempRownesneleri doğrudan kopyalamak israf olur çünkü her satır aynı şemaya sahiptir, bu nedenle çok sayıda yinelenen meta veri vardır. TempRowBunun yerine, tüm verileri tekil bir yapıya kopyalarız, böylece daha sonra gerekirse ayrı nesnelere kopyalayabilir veya OutputRowgerekirse iki veya daha fazla nesneye bölebiliriz.

'a benzer şekilde, TempRow' OutputRowdan biraz farklı olsa da bir başlık tanımı vardır TempRow. Daha önce açıklandığı gibi ilk değer, başlığın boyutudur, ancak bu değer daha büyüktür ve 1 yerine 2 bayt ayrılmıştır. Sonraki değer, içindeki bayt sayısıdır OutputRowve bu, 32 bitlik işaretsiz bir tamsayıdır. Bundan sonra sütun sayısıdır ve bu yalnızca tek bir bayttır. Ardından TempRow.

Başlıktan sonra, tüm veriler eklenir. , OutputRowher zaman bir veya daha fazla TempRowveya diğerinden OutputRowoluşturulduğundan, önek toplamı algoritmasını kullanarak her satırın veri boyutunu paralel olarak hesaplayabilir ve veri arabelleğine paralel olarak yazabiliriz.

Metal'de çalışırken OutputRow, statik olarak 1.000.000 baytlık sabit bir boyut olarak tahsis edilir. CPU'da daha verimli olabilir ve std::vectoryalnızca ihtiyacımız olan alan miktarını tahsis etmek için a kullanabiliriz.

Her iş parçacığının OutputRowparalel olarak okunmasını ve yazılmasını daha iyi kolaylaştırmak için, başlıkta olduğu gibi değişken boyutlu sütunların boyutlarının yazılması TempRowyerine, satır başına o sütunun verilerinin başına eklenirler. Örneğin, 2 tamsayı ve ardından 3 karakter "abc" içeren bir satır şu biçime sahip olacaktır: <integer><integer>3abc. (Şu anda yalnızca CPU üzerinde uygulanmaktadır) okuyucusu OutputRow, sütunun bir dize olduğunu bilir ve bu nedenle içeriğini okumak için dizenin başına atlayabilir. Her satırın boyutları satırlara yazılmaz.OutputRow. Bunun yerine, okuyucu arabelleği yineler ve her satırın başlangıcını ve her satır için her değişken boyutlu sütunun boyutlarını kaydeder. Bu, yerden tasarruf etmek için yapıldı, ancak başlığa veya satır başına yazılacak şekilde optimize edilebilir, böylece okuma OutputRowdaha verimli ve dolayısıyla daha hızlı olur. OutputRowCPU üzerindeki nesneleri okuma, bölme ve birleştirme ayrıntıları , Scheduler.

Gelecek iş

Mümkün olup olmadığını görmek için bu proje üzerinde bir deney olarak çalıştım. Onu üretime hazır hale getireceksem, hatta prototip üzerinde sahip olduğumdan daha fazla zaman harcayacaksam, uygulamak isteyeceğim birçok şey var.

O bir böcek

Çözmeyi çok istediğim ilk sorun (Xcode 13'te bir hata olduğuna inandığım şey), bir ThreadGroup içinde birden çok iş parçacığına iş parçacığı 0 atanıyor. Eğer herhangi bir fikriniz varsa bana bildirin. Bu, birden çok iş parçacığının üstbilgiyi denemesine ve yazmasına neden olur. Bu, iş parçacığının sırasına bağlı olarak başlığın verilerle kısmen sıkışmasına neden olur. Bu konuda Google'ı aramaya çalıştım, ancak özellikle yardımcı olan herhangi bir kaynak bulamadım. Her iş parçacığına ayırmaya çalıştığım bellek miktarıyla ilgili olduğunu düşünüyorum. Ne yazık ki Apple'ın resmi belgeleri bu konuda bulabildiğim hiçbir şey söylemiyor.

Sorgu Motoru + Ayrıştırıcı

Bir sonraki büyük görev, veritabanının SQL benzeri sorguları kabul edebilmesi ve bunları sorgu planlarına dönüştürüp çalıştırabilmesi için bir ayrıştırıcı ve sorgu motoru uygulamaktır. Bu görev ayrıca, diğer kitaplıklar ve programlar tarafından tüketilmek üzere bir DataFrame API'sinin uygulanmasını veya diske birden çok biçimde yazmayı içerir.

Katıl + Gruplandır

SQL spesifikasyonunu genişleterek, bir birleştirme ve bir Group By yan tümcesini hesaplayabilmek eğlenceli olurdu. Bir birleştirme gerçekleştirmenin saf yolunun, GPU'daki her ham satırı paralel olarak hesaplamak ve ardından CPU'da yığın başına bir kez karma birleştirme yapmak olduğunu düşündüm. Bununla birlikte, bunun yerine aynı anda katılmak istediğiniz 2 farklı tablodan bir yığın göndermenin bir yolunu bulmak ve GPU'nun birleştirilmiş satırları döndürmesini sağlamak daha verimli olabilir.

Group By için, bunu CPU'da yapabilir veya belki de GPU'da kısmi bir toplama yapabilirsiniz. Veya GPU'da ilk ham işlemeyi yaptığınız ve ardından bir dizi satır verildiğinde yürüttüğünüz farklı bir çekirdeğe sahip olduğunuz, küme içindeki her satır için grubu hesapladığınız bir kombinasyon yapabilirsiniz. Bu, grupları paralel olarak hesaplamak için GPU'nun paralel yapısından yararlanırken, satırları tutmak için daha fazla veri ayırabileceğiniz CPU'daki satırları hızlı bir şekilde toplamanıza olanak tanır.

Dağıtımlı sistem

Eğer bu sistem üretimde kullanılacaksa birden fazla makineden yararlanabilmesi gerekiyor. Birlikte çalışan Apple (ve Apple olmayan) bağlantılı cihazlardan oluşan heterojen bir ağ hayal edebiliyorum. Diğer makinelere komutlar gönderen ana bilgisayar denetleyicisi olarak bir iPhone ve her biri yerel olarak sahip oldukları veriler üzerinde işlem yapan ve işlenen satırları merkezi denetleyiciye geri gönderen bir grup iPad düşünün. Alternatif olarak, bir AWS lambda örneğindeki CPU'da veya şirket içinde bir Mac Pro sunucusuyla birden çok GPU'da aynı kodu çalıştıran bir bulut dağıtımınız olabilir. Bu sistemlerin tümü, hala çok fazla kullanılmamış işlem gücüne sahip olan (hissettiğim) cihazlarla çok büyük veri kümelerine çok hızlı yanıt veren erişim sağlamak için birlikte çalışabilir.

Bellek Ayak İzini Azaltın

Başka bir optimizasyon olarak, özellikle bunun Metal çalıştıran herhangi bir cihazda çalışmasını istediğim için, çalışan son kullanıcı uygulaması için cihazdaki kaynakları en üst düzeye çıkarabilmemiz için bellek ayak izini mümkün olduğunca küçük tutmak güzel olurdu. . İdeal olarak, bir dosya yığınını diskten belleğe okuyabilmeli, onu GPU'ya göndermek için arabelleğe dönüştürebilmeli ve ardından bu bellek yığınını boşaltabilmeliyiz. shared_ptrArabellekler için referans sayan bir bellek ayırma sistemim olacak şekilde kullanarak sistemi bu şekilde tasarlamaya çalıştım . Bununla birlikte, pratikte, kullandığım görev kitaplığının görev grafiğini birden çok girdiyle yeniden çalıştırması gerekip gerekmediğini bilmediğinden, kitaplığın arabelleğe yapılan referansı yakalayan lambdayı serbest bırakmadığını gördüm. Bu şu anlama gelir:shared_ptrlambda tarafından yakalanana hala başvurulur ve bu nedenle görev grafiği yok edilene kadar hafızasını boşaltmaz, bu yalnızca tüm grafiğin yürütülmesi bittiğinde gerçekleşir.

Çözüm

Genel olarak, bu proje üzerinde çalışırken ve düşünürken çok eğlendim. Yaptığım diğer birçok projeden çok farklıydı. Umarım bu makaleyi okumaktan keyif almışsınızdır. Tam uygulamam bu makalenin başında bağlantılıdır. Beğendiğiniz veya farklı yapmak istediğiniz şeyler hakkında yorumlarınız veya fikirleriniz varsa, lütfen benimle iletişime geçmekten çekinmeyin. Teşekkürler!