Search

In multilevel secret sharing, a secret is shared among a set of hierarchically organized participants in a way that the members of the superior compartments are more powerful and can replace the participants of an inferior one to form an authorized coalition during secret reconstruction. In this work, we first show that the only existing multilevel threshold secret sharing scheme based on the Chinese Remainder Theorem CRT is not secure and fails to work with certain natural threshold settings on compartments. As the main contribution, we propose a secure CRTbased scheme that works for all threshold settings. In the proposed scheme, we employ a refined version of Asmuth-Bloom secret sharing with a special and generic Asmuth-Bloom sequence called the anchor sequence. Based on this novel idea, we also propose the first multilevel conjunctive threshold secret sharing scheme based on the Chinese Remainder Theorem.

oşut bir uygulamanın görev etkileşim çizgesi komşu görevlerin farklı renklerle boyandığında birbirleri ile aynı renkteki görevler aynı anda pahalı bir senkronizasyon veri yapısı kullanılmadan aynı anda çalıştırılabilmektedir. Bu tür bir çalıştırmada bir renkteki görevler bitirilmeden, başka bir renkteki görev koşut halde şlenemeyeceğinden boyama esnasında kullanılan renk sayısı koşut uygulamanın çalıştırılması esnasında karşılaşılacak senkronizasyon adım sayısını belirtmektedir. Literatürde çizge boyama problemi ''bir çizgeyi mümkün olan en az sayıda renk kullanarak komşu noktalara farklı renkler vermek'' olarak tanımlanmıştır ve bir optimizasyon problemi olarakgörüldüğünde NP-Hard sınıfındadır. Çizge boyama probleminin farklı çeşitleri de paralel hesaplama, özellikle paralel bilimsel hesaplama alanında önemlidir. Problemin yukarıda bahsedilen basit halinde 1-uzaklık kullanılırken, k-uzaklık tanımı da özellikle k = 2 için pratikte kullanılmaktadır. Bu tezde de bu problem üzerine yoğunlaşılmıştır. Problemin genel hali ''bir çizgeyi mümkün olan en az sayıda renk kullanarak birbirinden k ve daha az uzaklıktaki nokta ikililerine farklı renkler vermek'' olarak tanımlanabilir. Literatürde bu problem için az renk kullanan buluşsal yöntemler önerilmiştir ve bu yöntemler k = 1 için oldukça hızlıdır. Fakat k = 2 için özellikle büyük çizgelerde bu buluşsalyöntemler dakikalar mertebesinde zaman alabilmektedirler. Çizge boyamanın bir uygulamanın çalışması için sadece bir ön işlem olduğu düşünüldüğünde bu işlemin getirdiği ekstra zamanın mümkün olduğu kadar az olması işlemin uygulanabilirliği için önemlidir. Bu tezde 2-uzaklık çizge boyama ve bu problemin farklı bir türü olan iki parçalı çizge boyama problemleri için iyimser ve açgözlü buluşsal yöntemler önerilmiştir. Bu yöntemler çok çekirdekli işlemcilerde ve Grafik İşleme Ünitelerinde koşut olarak gerçeklenmiş, ve ölçeklenebilirlikleri analiz edilmiştir. Yapılan deneylerde önerilen yöntemlerin ölçeklenebilir ve 16 çekirdek kullanıldığında literatürdeki yöntemlerden ortalama 25 kat hızlı oldukları görülmüş, özellikle sosyal ağ karakteri taşıyan çizgeler için büyük performansartışı sağladığı saptanmıştır. Yine bu tez çerçevesinde aynı renge sahip nokta kümelerinin eleman sayılarının birbirine yakın olması üzerine de çalışılmıştır. Bu tür dengeli dağılımlı bir boyama, uygulamanın çok çekirdekli işlemciler ve özellikle GİÜ'ler üzerinde çalışması esnasında her senkronizasyon adımında bütün çekirdekleri doyuracak kadar iş yükü olmasını sağlayacağından yüksek performans için önemli olabilmektedir. Bu tezde neredeyse hiç ekstra külfet getirmeden bunu sağlayabilecek iki yöntem önerilmiştir. Yapılan deneylerde bu yöntemlerin başarılı olduğu sonucuna varılmıştır. In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, the coloring stage is not free and the overhead can be significant. In particular, for distance-2 graph coloring (D2GC) and bipartite graph partial coloring (BGPC) problems, which have various use-cases within the scientific computing and numerical optimization domains, the coloring overhead can be in the order of minutes with a single thread for many real-life graphs, having millions and billions of vertices and edges.In this thesis, we propose a novel greedy algorithm for the distance-2 graph coloring problem on shared-memory architectures. We then extend the algorithm to bipartite graph partial coloring problem, which is structurally very similar to D2GC. The proposed algorithms yield a better parallel coloring performance compared to the existing shared-memory parallel coloring algorithms, by employing greedier and more optimistic techniques. In particular, when compared to the state-of-the-art, the proposed algorithms obtain 25x speedup with 16 cores, without decreasing the coloring quality. Moreover, we extend the existing distance-2 graph coloring algorithm to manycore architectures. Due to architectural limitations, the multicore algorithm can not easily be extended to manycore. Thus several optimizations and modifications are proposed to overcome such obstacles. In addition to multi and manycore implementations, we also offer novel optimizations for both D2GC and BGPC on social network graphs. Exploiting the structural properties of social graphs, we propose faster heuristics to increase the performance without decreasing the coloring quality. Finally, we propose two costless balancing heuristics that can be applied to both BGPC and D2GC, which would yield a better color-based parallelization performance with a better load-balancing, especially on manycore architectures. 92

Hiperçizge parçalama literatürde oldukça popüler bir problemdir. Dağıtık algoritmalar ve VLSI devre tasarımı gibi uygulamaların performasi bu yöntemle büyük ölçüde arttırılabilir. Son 20 yılda, hiperçizgeyi hızlı bir şekilde parçalayabilen araçlar geliştirilmiştir. Ancak bu problem NP-Zor olduğu için, bu araçlar sezgisel yöntemlere dayanmaktadır. Bu yüzden genelde optimal olmayan sonuçları bulmaktadırlar. Optimal hiperçizge problemi üzerine sezgisel yöntemlere dayalı çalışmalara nazaran çok daha az sayıda araştırma bulunmaktadır. Bu tezde, literatürdeki bir çok metriğe göre optimal parçalamayi bulan, PHaraoh isimli koşut hiperçizge parçalama aracı sunulmaktadır. Optimal sonuçların bulunması sayesinde, böyle bir araç, daha önceden geliştirilen hiperçizge parçalama araçlarının gerçek performansını, olası en iyi sonuçile karşılaştırarak ölçmemizi sağlar. PHaraoh herhangi bir parçalama ile başlatılabilir ve bu sonucu sürekli olarak geliştirmeye çalışır. Bu sayede, istenen optimal hiperçizge parçalama islemini verilen sürede tamamlayamasa bile, baslangıçta verilen parçalamanın kalitesini iyileştirebilir. Gerçek hayattaki uygulamalarda karşılaşılan hiperçizge modelleri üzerinde yaptığımız deneylere göre, PHaraoh pratikte en çok kullanılan araçların ürettiği parçalamaların kalitesini dal ve sınır arama yöntemini kullanarak büyük ölçüde iyileştirmektedir. Arama uzayında bulunan optimal parçalamanın bulunma süresini kısaltmak icin, `usta yamak` ve `iş çalma` yöntemlerine dayalı koşut algoritmalardan faydalandik. Daha önceki çalışmalarımızda ve bu tezde yaptığımız deneylere göre hiperçizge parçalama problemi icin dal ve sınır ağacındaki öğelerin sırası PHaraoh'ın performansını önemli oranda etkilemektedir. Bu tezde, değişik sıralama yöntemleri önerip, bunların PHaraoh'ın çalışma süresini nasıl değiştirdiğini ve bu değişikliğin nedenlerini hiperçizgelerin özelliklerine bağlayarak açıkladık. Hypergraph partitioning into K parts has many applications in practice such as distributed algorithms and very large scale integrated circuit (VLSI) design. There are various tools proposed in the literature which can partition a given hypergraph very fast. However, since the problem is NP-Hard and the traditional approaches heavily use heuristics, these tools do not provide an optimal partition. There is limited research on partitioning hypergraphs optimally. In this thesis, we proposePHaraoh, a parallel hypergraph partitioner that can provide optimal partitions for many metrics used in the literature. Such a partitioner is important in practice since it enables us to evaluate the true performance of the existing tools. Furthermore, PHaraoh can be started with an initial partition. Thanks to that, even an optimal solution is not found within the given time limit, PHaraoh improves the cost of the provided initial partition. Experimental results on hypergraphs obtained from real life matrices show that the quality of the partitions of existing tools can be improved significantly for most of the hypergraphs. In order to increase the speed up the search-space exploration, we experimented with both master-slave and work-stealing parallelization. It also has been shown that the runtime of the algorithm highly depends on the order of the items in the branch and bound tree. In this study, we propose different ordering strategies which can offer great speed ups depending on the characteristics of the hypergraph. 85

Karmaşık sistemlerin geliştirilmesinde, test etme en pahalı ve en çok zaman alan evredir. Model tabanlı testler yüksek kaliteli deney kurgusunu otomatik üretmede kullanılan yaklaşımlardan birisidir. Deney kurgusunu otomatik üretme test etmenin en zorlu parçalarından biridir. Sonlu durum makineleri ya da özdevinimler gibi biçimsel modeller, otomatik deney grubunu üretmek için kullanılmaktadır. Sistem belirli bir duruma senkronize edildikten sonra testler uygulanır ve bu belirli duruma gelebilmek için sıfırlama kelimeleri kullanılmaktadır. Daha kısa deney süreleri için en kısa sıfırlama kelimesini hesaplamak önemlidir, ancak en kısa sıfırlama kelimesini hesaplamak NP–hard bir problemdir. Bu nedenle kısa sıfırlama kelimelerini hesaplamak için sezgisel yöntemler kullanılmaktadır. GREEDY algoritması bu alanda bilinen en hızlı sezgisel algoritmadır. Bu tezde, GREEDY algoritmasını hızlandıran yaklaşımlar sunulmaktadır. İlk olarak GREEDY algoritmasının paralelleştirilmesine odaklanılmaktadır. İkinci olarak ise tembel bir yaklaşım önererek sıfırlama kelimesinin üretilmesi için gerekli bilgilerin hazırlanma süreci ertelenmektedir. Aynı zamanda, GREEDY algoritması için benzer algoritmik iyileştirilmeler önerilmektedir. Deney sonuçlarımız özdevinim büyüklügüne bağlı olarak GREEDY algoritmasının 500 kat daha hızlı hale getirilebileceğini göstermektedir. Önerilen geliştirmeler özdevinim büyüklügü arttıkça daha etkili hale gelmektedir. Testing is the most expensive and time consuming phase in the development of complex systems. Model–based testing is an approach that can be used to automate the generation of high quality test suites, which is the most challenging part of testing. Formal models, such as finite state machines or automata, have been used as specifications from which the test suites can be automatically generated. The tests are applied after the system is synchronized to a particular state, which can be accomplished by using a synchronizing word. Computing a shortest synchronizing word is of interest for practical purposes, e.g. for a shorter testing time. However, computing a shortest synchronizing word is an NP–hard problem. Therefore, heuristics are used to compute short synchronizing words. GREEDY is one of the fastest synchronizing heuristics currently known. In this thesis, we present approaches to accelerate GREEDY algorithm. Firstly, we focus on parallelization of GREEDY. Second, we propose a lazy execution of the preprocessing phase of the algorithm, by postponing the preparation of the required information until it is to be used in the reset word generation phase. We suggest other algorithmic enhancements as well for the implementation of the heuristics. Our experimental results show that depending on the automata size, GREEDY can be made 500⇥ faster. The suggested improvements become more effective as the size of the automaton increases. 52

Profesyonel ağlarda bireylerin birbirine tavsiye edilmesi bir bağlantı tahmini problemi olarak ele alınabilir. Bu amaç doğrultusunda öğrenme tabanlı yöntemler, hem tahmin hem de çıkarsama yapma hedefleri için uygundur. Bu yöntemlerin uygulanması kolaydır ve büyük ölçekli veri setleri için hesaplanabilirlik açısından da uygundurlar. Bu tezde, Türkiye'nin akademik işbirliği ağında, yazarların ve makalelerin önerilmesi için bağlantı tahmin modelleri araştırılmıştır. Modeller ve hipotezler için kavramsal bir arka plan oluşturmak amacıyla veri setini belirli görselleştirme araçları ve temel istatistikler kullanarak inceliyoruz. Bir yan ürün olarak, mevcut modellerin ve kullandıkları bilgi kaynaklarının olası eksikliklerini de vurguluyoruz. Kavramsal arka planı ve potansiyel dezavantajları hesaba katarak mevcut modelleri uyguluyor, karşılaştırıyor ve farklılıklarını ortaya koyuyor ve hipotezimizi test ediyoruz. Tüm bu modelleri eniyileme problemleri olarak ele alıyor ve birinci dereceden eniyileme yöntemlerini kullanarak çözüyoruz. Sonuçları, tahmin isabeti açısından değerlendiriyor ve anlamlarını da yorumluyoruz. Elde ettiğimiz sonuçlar, sahip olduğumuz veri seti için özel olsa da, kullandığımız teknikler diğer ağ veri setleri ile uygulanabilecek kadar geneldir. Recommendation of individuals in a professional network can be thought as a link prediction problem. For this purpose, learning based methods are suitable for both prediction and inference goals. These methods are also easy to implement and they are computationally tractable for large scale datasets. In this thesis, we investigate link prediction models for recommendation of authors and papers in academic collaboration network of Turkey. We examine the dataset with certain visualization tools and basic statistics, in order to form a conceptual background for our models and hypothesis. As a byproduct, we highlight potential drawbacks of existing models and the information resources they use. Taking the conceptual background and potential drawbacks into account, we implement, compare and contrast existing models, and test our hypothesis. We cast all of these models as optimization problems and solve them by using first order optimization methods. We evaluate their results in terms of prediction accuracy and provide interpretation about their meaning as well. While the results that we have obtained are special for the given dataset that we have, techniques that we have used are generic enough to be implemented with other graph datasets. 45

Günümüzde, veri setlerinin boyutundaki artış ile tavsiye sistemleri gibi uygulamalardaki bu verilerle çalışmayı sağlayacak hızlı ve tutarlı araçların gereksinimi, en kısa sürede tüm kaynakları kullanarak istenen çalışmaları yapabilen yeni düzenlenmiş modeller üzerinde büyük bir ilgi oluşmasını sağladı.Bu çalışmada, paralelleşmiş büyük ölçekli matris faktorizasyon problemi için bir sistem oluşturduk.Bu tür problemleri çözmek için en çok kullanılan, en başarılı yöntemlerden biri optimizasyon teknikleridir. Optimizasyon yöntemleri, iterasyonları gerçekleştirmek için gradyan vektörlerine gerek duymaktadır. Bu tür problemlerin çözümünde zamanın çoğu gradyan ve fonksiyon değerlerinin hesaplanmasında harcanmaktadır. Bu çalışmada, matris faktorizasyonunda daha önce kullanılmayan, yeni bir yöntem uyguladık. Paralelizasyon için CPU ve GPU uygulamalarını gösterdik. Çalışmamızda da görüldüğü gibi, önerilen paralelizasyon oldukça iyi ölçeklenmektedir. MovieLens veri seti üzerindeki çalışmamızı raporladık. Sonuçlarımız gösteriyor ki iterasyon sayısını azaltmada önerdiğimiz yöntem oldukça başarılı. İstenilen RMSE değerleri ile birlikte umut vadeden ölçeklenir değerlere ulaştık. During recent years, the exponential increase in data sets' sizes and the need for fast and accurate tools which can operate on these huge data sets in applications such as recommendation systems has led to an ever growing attention towards devising novelmethods which can incorporate all the available resources to execute desired operations in the least possible time. In this work, we provide a framework for parallelized large-scale matrix factorization problems. One of the most successful and used methods to solve these problems is solving them via optimization techniques. Optimization methods require gradient vectors to update the iterates. The time spent to solve such a problem is mostly spent on calls to gradient and function value evaluations. In this work, we have used a recent method, which has not been used before for matrix factorization. When it comes to parallelization, we present both CPU and GPU implementations. As our experiments show, the proposed parallelization scales quite well. We report our results on Movie- Lens data set. Our results show that the new method is quite successful in reducing the number of iterations. We obtain very good RMSE values with significant promising scaling figures. 54