Theses supervised by Prof. Dr. Cevdet Aykanat
43 theses · İhsan Doğramacı Bilkent University
Dağıtık bellek sistemlerinde 1D düğüm paralel GNN eğitiminin performansının iyileştirilmesi
Graph Neural Networks (GNNs) are pivotal for analyzing data within graph structured domains such as social media, biological networks, and recommendation systems. Despite their advantages, scaling GNN training to large datasets in distributed settings poses significant challenges due to the complex task of managing computation and communication costs. The objective of this work is to scale 1D vertex-parallel GNN training on distributed memory systems via (i) two-constraint partitioning formulation for better computational load balancing and (ii) overlapping communication with computation for reducing communication overhead. In the proposed two-constraint formulation, one constraint encodes the computational load balance during forward propagation, whereas the second constraint encodes the computational load balance during backward propagation. We propose three communication and computation overlapping methods that perform overlapping at three different levels. These methods were tested against traditional approaches using benchmark datasets, demonstrating improved training efficiency without altering the model structure. The outcomes indicate that multi-constraint graph partitioning and the integration of communication and computation overlapping schemes can significantly mitigate the challenges of distributed GNN training. The research concludes with recommendations for future work, including adapting these techniques to dynamic and more complex GNN architectures, promising further improvements in the efficiency and applicability of GNNs in real-world scenarios.
Dağıtık-bellekli sistemlerde paralel çizge sinir ağları eğitimini hızlandırmak için yeni model ve yöntemler
Graph Neural Networks (GNNs) have emerged as effective tools for learning from graph-structured data across diverse application domains. Despite their success, the scalability of GNNs remains a critical challenge, particularly in full-batch training on large-scale, irregularly sparse, and scale-free graphs. Traditional one-dimensional (1D) vertex-parallel training strategies, while widely adopted, often suffer from severe load imbalance and excessive communication overhead, limiting their performance on distributed-memory systems. This thesis addresses the scalability limitations of 1D approaches by investigating alternative partitioning strategies for parallelization that better exploit the structure of modern graph workloads. A systematic evaluation framework is developed to assess parallel GNN training performance across a range of datasets with varying sparsity and degree distributions. The framework captures key performance indicators such as computational load balance, inter-process communication volume, and parallel runtime. Extensive experiments are conducted on two Tier-0 supercomputers, LUMI and MareNostrum5, using hundreds of real-world graph instances. On average of 22 well-known GNN datasets, the results show up to 61% decrease in total communication volume and up to 39% decrease in parallel runtime compared to 1D partitioning strategies on 1024 processes. These improvements are consistent across graphs with high variance in degree and sparsity, confirming the robustness of the proposed approaches. The findings demonstrate the potential of moving beyond traditional 1D paradigms and provide practical insights into scalable and communication-efficient GNN training on distributed platforms.
Gecikme verimli sakla-ve-yönlendir şemasında iletişim hacmi artışının azaltılması
Sparse matrix operations such as sparse matrix-vector (SpMV) are latency bound applications where number of messages sent by processors dominate the overall communication overhead. In prior work, Store and Forward (STFW) scheme was proposed and implemented to scale such fine-grain operations as SpMV by operating on specialized Virtual Process Topologies (VPTs). However, the STFW scheme incur an increase in the communication volume due to the STFW overhead. This increase in total communication volume disturbs the scalability of the STFW scheme, especially in sparse matrix-matrix (SpMM) kernels where a sparse matrix is post-multiplied by a tall-and-skinny dense matrix. In this work, we propose and implement a Kernighan-Lin-based (KL) heuristic to iteratively improve the one-to-one mapping produced by the initial task partition. The objective of this heuristic is to reduce the increase in the total communication volume to be incurred by the STFW scheme in SpMV, and SpMM type of kernels. We evaluated the effectiveness of the proposed KL-based heuristic in improving the Total Communication Volume and Maximum Weighted Communication Volume metrics through experimental performance comparisons using VPTs of various dimensions and constructive mapping methods.
Çok düzeyli yapıyı kullanarak paralel akış çizelge bölümleme
Graph partitioning is widely used for efficient parallelization of a variety of applications. Streaming graph partitioning is a one pass partitioning solution provided to overcome high computation costs of offline graph partitioners. Even though these streaming algorithms can be used for successively repartitioning, aiming at further improvements in partitioning qualities, quality improvements is limited to few passes that make offline graph partitioning tools still a desirable solution for graph partitioning due to the generated high-quality partitions. We propose a multilevel approach using streaming algorithms that can alleviate the tradeoff between quality and performance in graph partitioning problem. Moreover, our OpenMP based multi-threaded implementation can generate fast and highly scalable solutions compared to mt-metis, a multi-threaded solution for METIS, and the state-of-the-art offline high-quality graph partitioning tool. Our results show that our method can produce up to fifteen times faster and more scalable results in large graph datasets. We also show that our method can improve the quality of partitions significantly compared to state-of-the-art streaming graph partitioning algorithm LDG after repartitioning several times. On average we produce partitions with 29% better qualities than the LDG algorithm.
Eş zamanlı hesaplama ve veri yükü dengeleme için çizge/hiperçizge bölümleme modelleri
In the literature, several successful partitioning models and methods have been proposed and used for computational load balancing of irregularly sparse appli- cations on distributed-memory architectures. However, the literature lacks par- titioning models and methods that encode both computational and data load balancing of processors. In this thesis, we try to close this gap by proposing graph and hypergraph partitioning models and methods that simultaneously en- code computational and data load balancing of processors. The validity of the proposed models and methods are tested on two widely-used irregularly sparse applications: parallel mesh simulations and parallel sparse matrix sparse matrix multiplication.
Öneri sistemleri için olasılıksal eğim iniş ile matris çarpanlarına ayırma
Matrix factorization is an efficient technique used for disclosing latent features of real-world data. It finds its application in areas such as text mining, image analysis, social network and more recently and popularly in recommendation systems. Alternating least squares (ALS), stochastic gradient descent (SGD) and coordinate descent (CD) are among the methods used commonly while factorizing large matrices. SGD-based factorization has proven to be the most successful among these methods after Netflix and KDDCup competitions where the winners' algorithms relied on methods based on SGD. Parallelization of SGD then became a hot topic and studied extensively in the literature in recent years. We focus on parallel SGD algorithms developed for shared memory and distributed memory systems. Shared memory parallelizations include works such as HogWild, FPSGD and MLGF-MF, and distributed memory parallelizations include works such as DSGD, GASGD and NOMAD. We design a survey that contains exhaustive analysis of these studies, and then particularly focus on DSGD by implementing it through message-passing paradigm and testing its performance in terms of convergence and speedup. In contrast to the existing works, many real-wold datasets are used in the experiments that we produce using published raw data. We show that DSGD is a robust algorithm for large-scale datasets and achieves near-linear speedup with fast convergence rates.
İndirgeme işlemlerinde gönderme yükünün dengelenmesi
We investigate balancing send volume in applications that involve reduce operations. In such applications, a given computational-task-to-processor mapping produces partial results generated by processors to be reduced possibly by other processors, thus incurring inter-processor communication. We define the reduce communication task assignment problem as assigning the reduce communication tasks to processors in a way that minimizes the send volume load of the maximally loaded processor. We propose one novel independent-task-assignment-based algorithm and four novel bin-packing-based algorithms to solve the reduce communication task assignment problem. We validate our proposed algorithms on two kernel operations: sparse matrix-sparse matrix multiplication (SpGEMM) and sparse matrix-matrix multiplication (SpMM). Experimental results show improvements of up to 23% on average for the maximum communication volume cost metric in SpGEMM and up to 12% improvement on average in SpMM.
Gecikim-limitli paralel uygulamalarda işlemciler arası mesaj paylaşım yöntemiyle performans iyileştirme
The performance of paralellized High Performance Computing (HPC) applications is tied to the efficiency of the underlying processor-to-processor communication. In latency-bound applications, the performance runs into bottleneck by the processor that is sending the maximum number of messages to the other processors. To reduce the latency overhead, we propose a two-phase message-sharing-based algorithm, where the bottleneck processor (the processor sending the maximum number of messages) is paired with another processor. In the first phase, the bottleneck processor is paired with the processor that has the maximum number of common outgoing messages. In the second phase, the bottleneck processor is paired with the processor that has the minimum number of outgoing messages. In both phases, the processor pair share the common outgoing messages between them, reducing their total number of outgoing messages, but especially the number of outgoing messages of the bottleneck processor. We use Sparse Matrix-Vector Multiplication as the kernel application and a 512-processor setting for the experiments. The proposed message-sharing algorithm achieves a reduction of 84% in the number of messages sent by the bottleneck processor and a reduction of 60% in the total number of messages in the system.
Olasılıksal gradyan alçalmanın hibrit paralelleştirilmesi
The purpose of this study is to investigate the efficient parallelization of the Stochastic Gradient Descent (SGD) algorithm for solving the matrix completion problem on a high-performance computing (HPC) platform in distributed memory setting. We propose a hybrid parallel decentralized SGD framework with asynchronous communication between processors to show the scalability of parallel SGD up to hundreds of processors. We utilize Message Passing Interface (MPI) for inter-node communication and POSIX threads for intra-node parallelism. We tested our method by using four different real-world benchmark datasets. Experimental results show that the proposed algorithm yields up to 6 times better throughput on relatively sparse datasets, and displays comparable performance to available state-of-the-art algorithms on relatively dense datasets while providing a flexible partitioning scheme and a highly scalable hybrid parallel architecture.
Paylaşılan bellek mimarisinde gerçekleştirilen paralel seyrek matris-vektör ve devrik-matris-vektör çarpımında veri yeniden kullanımını arttırmak
Sparse matrix-vector and matrix-transpose-vector multiplications (Sparse AATx) are the kernel operations used in iterative solvers. Sparsity pattern of the input matrix A, as well as its transpose, remains the same throughout the iterations. CPU cache could not be used properly during these Sparse AA T x operations due to irregular sparsity pattern of the matrix. We propose two parallelization strategies for Sparse AA T x. Our methods partition A matrix in order to exploit cache locality for matrix nonzeros and vector entries. We conduct experiments on the recently-released Intel Xeon Phi coprocessor involving large variety of sparsematrices. Experimental results show that proposed methods achieve higher performance improvement than the state-of-the-art methods in the literature.
Seyrek üçgensel sistemlerin önbellek yerelliğine göre yeniden sıralanması
Sparse Triangular Solve (SpTS) is a commonly used kernel in a wide variety of scientific and engineering applications. Efficient implementation of this kernel on current architectures that involve deep cache hierarchy is crucial for attaining high performance. In this work, we propose an effective framework for cache-aware SpTS. Solution of sparse linear symmetric systems utilizing the direct methods require the triangular solve of the form LUz = b, where L is lower triangular factor and U is upper triangular factor. For cache utilization, we reorder the rows and columns of the L factor regarding the data dependencies of the triangular solve. We represent the data dependencies of the triangular solve as a directed hypergraph and construct an ordered partitioning model on this structure. For this purpose, we developed a variant of Fiduccia-Mattheyses (FM) algorithm which respects the dependency constraints. We also adopt the idea of splitting L factors into dense and sparse components and solving them seperately with different autotuned kernels for achieving more flexibility in this process. We investigate the performance variation of different storage schemes of L factors and the corresponding sparse and dense components. We utilize autotuning provided by Optimized Sparse Kernel Interface (OSKI) to reduce performance degradation that incurs due to the gap between processors and memory speeds. Experiments performed on real-world datasets verify the effectiveness of the proposed framework.
Paylaşımlı hafıza sistemleri için parallel seyrek matris - dizi çarpım teknikleri
SpMxV (Sparse matrix vector multiplication) is a kernel operation in linear solvers in which a sparse matrix is multiplied with a dense vector repeatedly. Due to random memory access patterns exhibited by SpMxV operation, hardware components such as prefetchers, CPU caches, and built in SIMD units are under-utilized. Consequently, limiting parallelization efficieny. In this study we developed; • an adaptive runtime scheduling and load balancing algorithms for shared memory systems, • a hybrid storage format to help effectively vectorize sub-matrices, • an algorithm to extract proposed hybrid sub-matrix storage format. Implemented techniques are designed to be used by both hypergraph partitioning powered and spontaneous SpMxV operations. Tests are carried out on Knights Corner (KNC) coprocessor which is an x86 based many-core architecture employing NoC (network on chip) communication subsystem. However, proposed techniques can also be implemented for GPUs (graphical processing units).
Paralel seyrek matris-matris çarpımı için hiperçizge modelleri
Multiplication of two sparse matrices (i.e., sparse matrix-matrix multiplication, which is abbreviated as SpGEMM) is a widely used kernel in many applications such as molecular dynamics simulations, graph operations, and linear programming. We identify parallel formulations of SpGEMM operation in the form of C = AB for distributed-memory architectures. Using these formulations, we propose parallel SpGEMM algorithms that have the multiplication and communication phases: The multiplication phase consists of local SpGEMM computations without any communication and the communication phase consists of transferring required input/output matrices. For these algorithms, three hypergraph models are proposed. These models are used to partition input and output matrices simultaneously. The input matrices A and B are partitioned in one dimension in all of these hypergraph models. The output matrix C is partitioned in two dimensions, which is nonzero-based in the first hypergraph model, and it is partitioned in one dimension in the second and third models. In partitioning of these hypergraph models, the constraint on vertex weights corresponds to computational load balancing among processors for the multiplication phase of the proposed SpGEMM algorithms, and the objective, which is minimizing cutsize defined in terms of costs of the cut hyperedges, corresponds to minimizing the communication volume due to transferring required matrix entries in the communication phase of the SpGEMM algorithms. We also propose models for reducing the total number of messages while maintaining balance on communication volumes handled by processors during the communication phase of the SpGEMM algorithms. An SpGEMM library for distributed memory architectures is developed in order to verify the empirical validity of our models. The library uses MPI (Message Passing Interface) for performing communication in the parallel setting. The developed SpGEMM library is run on SpGEMM instances from various realistic applications and the experiments are carried out on a large parallel IBM BlueGene/Q system, named JUQUEEN. In the experimentation of the proposed hypergraph models, high speedup values are observed.
Seyrek işlemlerin ölçeklenebilmesi için gecikim-merkezli model ve yöntemler
Parallelization of sparse kernels and operations on large-scale distributed memory systems remains as a major challenge due to ever-increasing scale of modern high performance computing systems and multiple conflicting factors that affect the parallel performance. The low computational density and high memory footprint of sparse operations add to these challenges by implying more stressed communication bottlenecks and make fast and efficient parallelization models and methods imperative for scalable performance. Sparse operations are usually performed with structures related to sparse matrices and matrices are partitioned prior to the execution for distributing computations among processors. Although the literature is rich in this aspect, it still lacks the techniques that embrace multiple factors affecting communication performance in a complete and just manner. In this thesis, we investigate models and methods for intelligent partitioning of sparse matrices that strive for achieving a more correct approximation of the communication performance. To improve the communication performance of parallel sparse operations, we mainly focus on reducing the latency bottlenecks, which stand as a major component in the overall communication cost. Besides these, our approaches consider already adopted communication cost metrics in the literature as well and aim to address as many cost metrics as possible. We propose one-phase and two-phase partitioning models to reduce the latency cost in one-dimensional (1D) and two-dimensional (2D) sparse matrix partitioning, respectively. The model for 1D partitioning relies on the commonly adopted recursive bipartitioning framework and it uses novel structures to capture the relations that incur latency. The models for 2D partitioning aim to improve the performance of solvers for nonsymmetric linear systems by using different partitions for the vectors in the solver and uses that flexibility to exploit the latency cost. Our findings indicate that the latency costs should definitely be considered in order to achieve scalable performance on distributed memory systems.
Paralel seyrek matris vektör çarpımında uzaysal ve zamansal yerelliği kullanmak için sıralma yöntemleri
Sparse Matrix-Vector multiplication (SpMV) is a very important kernel opera- tion for many scientific applications. For irregular sparse matrices, the SpMV operation suffers from poor cache performance due to the irregular accesses of the input vector entries. In this work, we propose row and column reordering methods based on Graph partitioning (GP) and Hypergraph partitioning (HP) in order to exploit spatial and temporal localities in accessing input vector entries by clustering rows/columns with a similar sparsity pattern close to each other. The proposed methods exploit spatial and temporal localities separately (using either rows or columns of the matrix in a GP or HP method), simultaneously (using both rows and column) and in a two-phased manner(using either rows or columns in each phase). We evaluate the validity of the proposed models on a 60- core Xeon Phi co-processor for a large set of sparse matrices arising from different applications. The performance results confirm the validity and the effectiveness of the proposed methods and models.
Büyük ölçekli paralel SyGEMM'de iletişim hacmini düşürme
Sparse matrix-matrix multiplication of the form of C = A x B, C = A x A and C = A x AT is a key operation in various domains and is characterized with high complexity and runtime overhead. There exist models for parallelizing this operation in distributed memory architectures such as outer-product (OP), inner-product (IP), row-by-row-product (RRP) and column-by-column-product (CCP). We focus on row-by-row-product due to its convincing performance, row preprocessing overhead and no symbolic multiplication requirement. The parallelization via row-by-row-product model can be achieved using bipartite graphs or hypergraphs. For an efficient parallelization, we can consider multiple volume-based metrics to be reduced such as total volume, maximum volume, etc. Existing approaches for RRP model do not encapsulate multiple volume-based metrics. In this thesis, we propose a two-phase approach to reduce multiple volume-based cost metrics. In the rst phase, total volume is reduced with a bipartite graph model. In the second phase, we reduce maximum volume while trying to keep the increase in total volume as small as possible. Our experiments show that the proposed approach is effective at reducing multiple volume-based metrics for different forms of SpGEMM operations.
Seyrek matris hesaplamalarında performans iyileşmesi için özyinelemeli ikiye bölümleme modelleri
Sparse matrix computations are among the most important building blocks of linear algebra and arise in many scientific and engineering problems. Depending on the problem type, these computations may be in the form of sparse matrix dense matrix multiplication (SpMM), sparse matrix vector multiplication (SpMV), or factorization of a sparse symmetric matrix. For both SpMM and SpMV performed on distributed-memory architectures, the associated data and task partitions among processors affect the parallel performance in a great extent, especially for the sparse matrices with an irregular sparsity pattern. Parallel SpMM is characterized by high volumes of data communicated among processors, whereas both the volume and number of messages are important for parallel SpMV. For the factorization performed in envelope methods, the envelope size (i.e., profile) is an important factor which determines the performance. For improving the performance in each of these sparse matrix computations, we propose graph/hypergraph partitioning models that exploit the advantages provided by the recursive bipartitioning (RB) paradigm in order to meet the specific needs of the respective computation. In the models proposed for SpMM and SpMV, we utilize the RB process to enable targeting multiple volume-based communication cost metrics and the combination of volume- and number-based communication cost metrics in their partitioning objectives, respectively. In the model proposed for the factorization in envelope methods, the input matrix is reordered by utilizing the RB process in which two new quality metrics relating to profile minimization are defined and maintained. The experimantal results show that the proposed RB-based approach outperforms the state-of-the-art for each mentioned computation.
Paralel ağ tarayıcıları için sayfa atama yöntemleri
ABSTRACTPAGE-TO-PROCESSOR ASSIGNMENT TECHNIQUESFOR PARALLEL CRAWLERSAta Tü rkuM.S. in Computer EngineeringSupervisor: Prof. Dr. Cevdet AykanatSeptember, 2004In less than a decade, the World Wide Web has evolved from a research projectto a cultural phenomena eï¬ective in almost every facet of our society. The increasein the popularity and usage of the Web enforced an increase in the eï¬ciency ofinformation retrieval techniques used over the net. Crawling is among such tech-niques and is used by search engines, web portals, and web caches. A crawler is aprogram which downloads and stores web pages, generally to feed a search engineor a web repository. In order to be of use for its target applications, a crawlermust download huge amounts of data in a reasonable amount of time. Gener-ally, the high download rates required for eï¬cient crawling cannot be achievedby single-processor systems. Thus, existing large-scale applications use multipleparallel processors to solve the crawling problem. Apart from the classical paral-lelization issues such as load balancing and minimization of the communicationoverhead, parallel crawling poses problems such as overlap avoidance and earlyretrieval of high quality pages. This thesis addresses parallelization of the crawl-ing task, and its major contribution is mainly on partitioning/page-to-processorassignment techniques applied in parallel crawlers. We propose two new page-to-processor assignment techniques based on graph and hypergraph partitioning,which respectively minimize the total communication volume and the number ofmessages, while balancing the storage load and page download requests of proces-sors. We implemented the proposed models, and our theoretic approaches havebeen supported with empirical ï¬ndings. We also implemented an eï¬cient parallelcrawler which uses the proposed models.Keywords: Parallel crawling, graph partitioning, hypergraph partitioning, pageassignment.iii
Yinelemeli iyileştirme tabanlı buluşsal yöntemlerin ortak dosya kullanan görevlerin türdeş olmayan istemci sunucu ortamlarında uyarlamalı zamanlamasında kullanımı
ÃÃà ÃÃà à ÃÃà ¹Ãà ÃÃÇà à Ãù à à ÃÃÃÃÃà ÃÇà ÃÃÃà à à ÃÃÃÃ Ç Ã ÃÃà Ãà ÃÃÃÃà à Çà à à ÃÇ Ã ÇÃà à Ãà ùÃà ÃÃÃÃÃÇÃà ÃÃÃà à Öà İà ºÃº à ÃÃÃÃÃ Ö Ã Ã ÖÃÃÃà Öà ÃÃÖ ÃÖà º Öº Ã Ã İ ÃÃà ÃÃÃş ¾¼¼à à Ãà à à à Ãà Ãà Ãà ¬à ¹à Öà à à à Ãà à Öà à ÃÃà à Ãà Ö¹Ãà à Ãà à ÃÖÃà ÃÖ ÃÃÃİ ÃÃà ÃÃÃÖà Ãà ÃÃà à ÃÃÃ Ã Ö Ãà ÖÃÃà ÃÃúà à Ãà à ÃÖ Ãà ÃÖ ÃÃÃİ ÃÖÃÃÃà ÃÖ Ã Ã ÃÖÃ Ã Ã Ö Ãà ÃÃÃÃÖà à à Ãà ÃÃÖ Ã Ã Ãà ÃÃÃÃÃ Ö İ Ö Ã Ö ÃÃ Û Ã Ã Ã Ãà à ÃÃà Ãà ÖİÃÃÃà à Ãà à à à Ãà à à à à à ú à à ÃÛ Ã ÃÃ Ã Ö İ Ã ÃÃ Ö Ã Ö ÃÃà à ÃÖà Ãà à à à ÜÃÃà à à à ¬à ¹à Öà ÃÃ Ö Ã Ãà ÃÃà à à ÃÃà ÃùÃà à Ãà à à à ÃÃ Ã Ö Ã Ãà à Ãà ÜÃÖ Ãà Ãà Ãà Ûà à à ÃÃ Ö Ã Ãúà ÃÖÃÃÃà ÃÖ Â¹Ã Ã Ã Ãà à ÃÃÖÃ Û ÃÃÃÃà à à à Ãà à Ãà ùà ÃÃş Ö Â¬Ã Ã ÃÃ Ã Ü Ãà Ãà ÃÖ Öà à à ú ÃÖ Ã Ö Â¬Ã Ã ÃÃ Ã ÃşÛÃà Ãà ÃÖ Ã ÃÃà à Ãà à İÃ Ö Ö Ã Ã Ûà à à Ãà İÃ Ö Ö Ã Â¹Ã Öà à Ãà à ¹à ÃÖÃÃà à ÃÃş Û ÃÖÃÃÃà Ãà ÃÃ Ã Ö Ã Ã Â¹ ÃÃÖÃà à Ãà ÃÃÖ Ãà à ÃÖ Ö Â¬Ã Ã Ã Ãà Ãà Ãà ÃÃà ÃÖ Ã Ãà ÃÛà ÃÃà à à Ãà Ãà ¹à ÃÃú ÃÃà à Ãà à à Ãà à ÃÃÃş à ÃÃÃÃà à Ãà à ÃÖÃÃÃà à ÃÃÃà à ÃÃà à ÃÃà ÃÃ Ã Ã Ö Ã Ã Â¹ ÃÃÖÃà à Ãù à ÃÖ Ãà à Ãà Ãà ÃÃÃİşÃÃ Ã Ö Â« à à à Ãà à à Ãİ Ãà Ãà à ÃÃÃÃà à Ãà à à à ÃÃÃà à Ãú ÜÃ Ö Ã ÃÃ Ã Ö ÃÃÃÃà ÃÃ Û Öà à ÃİÃà à ÃÃİ ÃÖà à Öùà ÃÃà à Ãà Ö¹ÃÃ Ã Ö Ã ÛÃÖ Ã Ã ÃÛ Ã Ãà ÃÖÃÃÃà ÃÖ Â¹Ã Ã Ã Ãà ÃÃÃÖÃ Ã Ö ÃÖÃà Ãà ÃÃ Ö Ã ÃÃ Ö İ ÃÃÃÃÖà à à ÃÃÖà ºà İÛÃÖ Ã Ãà à Ãà à ş ¬à ¹à ÖÃ Ã Ã Ãş à Öà à ÃÃà à Ãà Ö¹Ãà à Ãà ùÃÖÃÃş Ã Ö Ã Ã Â¹ ÃÃÖÃà à Ãú
Paralel seyrek matris-vektör çarpımı ve dolaylı yöntemler
parse matrix-vector multiply (SpMxV) operations are in the kernel of manyscientiï¬c computing applications. Therefore, eï¬cient parallelization of SpMxVoperations is of prime importance to scientiï¬c computing community. Previousworks on parallelizing SpMxV operations consider maintaining the load balanceamong processors and minimizing the total message volume. We show that the to-tal message latency (start-up time) may be more important than the total messagevolume. We also stress that the maximum message volume and latency handledby a single processor are important communication cost metrics that should beminimized. We propose hypergraph models and hypergraph partitioning methodsto minimize these four communication cost metrics in one dimensional and twodimensional partitioning of sparse matrices. Iterative methods used for solvinglinear systems appear to be the most common context in which SpMxV operationsarise. Usually, these iterative methods apply a technique called preconditioning.Approximate inverse preconditioningâwhich can be applied to a large class ofunsymmetric and symmetric matricesâreplaces an SpMxV operation by a se-ries of SpMxV operations. That is, a single SpMxV operation is only a piece of alarger computation in the iterative methods that use approximate inverse precon-ditioning. In these methods, there are interactions in the form of dependenciesbetween the successive SpMxV operations. These interactions necessitate parti-tioning the matrices simultaneously in order to parallelize a full step of the subjectclass of iterative methods eï¬ciently. We show that the simultaneous partitioningrequirement gives rise to various matrix partitioning models depending on theiterative method used. We list the partitioning models for a number of widelyused iterative methods. We propose operations to build a composite hypergraphby combining the previously proposed hypergraph models and show that par-titioning the composite hypergraph models addresses the simultaneous matrixpartitioning problem. We strove to demonstrate how the proposed partitioningivvmethodsâboth the one that addresses multiple communication cost metrics andthe other that addresses the simultaneous partitioning problemâhelp in practice.We implemented a library and investigated the performances of the partitioningmethods. These practical investigations revealed a problem that we call messageordering problem. The problem asks how to organize the send operations to min-imize the completion time of a certain class of parallel programs. We show howto solve the message ordering problem optimally under reasonable assumptions.Keywords: Sparse matrices, parallel matrix-vector multiplication, iterative meth-ods, preconditioning, approximate inverse preconditioner, hypergraph partition-ing.
Sayfadeğeri hesaplamasının etkin olarak paralelleştirilmesi için ağ sitesi tabanlı bölümleme yöntemleri
Web search engines use ranking techniques to order Web pages in query results. PageRank is an important technique, which orders Web pages according to the linkage structure of the Web. The efficiency of the PageRank computation is important since the constantly evolving nature of the Web requires this computation to be repeated many times. PageRank computation includes repeated iterative sparse matrix-vector multiplications. Due to the enormous size of the Web matrix to be multiplied, PageRank computations are usually carried out on parallel systems. However, efficiently parallelizing PageRank is not an easy task, because of the irregular sparsity pattern of the Web matrix. Graph and hypergraphpartitioning-based techniques are widely used for efficiently parallelizing matrixvector multiplications. Recently, a hypergraph-partitioning-based decomposition technique for fast parallel computation of PageRank is proposed. This technique aims to minimize the communication overhead of the parallel matrix-vector multiplication. However, the proposed technique has a high prepropocessing time, which makes the technique impractical. In this work, we propose 1D (rowwise and columnwise) and 2D (fine-grain and checkerboard) decomposition models using web-site-based graph and hypergraph-partitioning techniques. Proposed models minimize the communication overhead of the parallel PageRank computations with a reasonable preprocessing time. The models encapsulate not only the matrix-vector multiplication, but the overall iterative algorithm. Conducted experiments show that the proposed models achieve fast PageRank computation with low preprocessing time, compared with those in the literature. Keywords: PageRank, Parallel Sparse-Matrix Vector Multiplication, Graph and Hypergraph Partitioning.
ParPaToH: Bir 2-boyutlu paralel hiperçizge bölümleme aracı
Hypergraph partitioning is a process that is being used to ï¬nd solutions foroptimization problems in various areas, including parallel volume rendering, par-allel information retrieval and VLSI circuit design. While the current partitioningmethods are adequate for hypergraphs up to certain size, these methods start tofail once the problem size exceeds this threshold.In this thesis we introduce ParPaToH, a parallel p-way hypergraph partition-ing tool that makes use of a 2-D decomposition to reduce the communicationoverhead and implements a parallel-computing friendly version of the acceptedmulti-level partitioning paradigm to generate its partitioning. We present newconcepts in hypergraph partitioning that lead to a coarse-grain parallel solution.Finally, we discuss the implementation of the tool in detail and present experi-mental results to demonstrate its eï¬ectiveness.Keywords: Multilevel hypergraph partitioning, parallel computing.iii
Zamansal sürümlendirilmiş doküman koleksiyonlarında paralel metin erişimi
In recent years, as the access to the Internet is getting easier andcheaper, the amount and the rate of change of the online datapresented to the Internet users are increasing at an astonishingrate. This ever-changing nature of the Internet causes anever-decaying and replenishing information collection where newlypresented data generally replaces old and sometimes valuable data.There are many recent studies aiming to preserve this valuabletemporal data and size and number of temporal Web data collectionsare increasing. We believe that soon, information retrieval systemsresponding to time-range queries in a reasonable amount of time willemerge as a means of accessing vast temporal Web data collections.Due to tremendous size of temporal data and excessive number ofquery submissions per unit time, temporal information retrievalsystems will have to utilize parallelism as much as possible.In parallel systems, in order to index collections using invertedindices, a strategy on distribution of the inverted indices has tobe followed. In this study, the feasibility of time-basedpartitioned versus term-based partitioned temporal-webinverted-indices is analyzed and a novel parallel text retrievalsystem for answering temporal web queries is implemented consideringthe number of queries processed in unit time. Moreover, weinvestigate the performance of skip-list based and randomized-selectbased ranking schemes on time-based and term-based partitionedinverted indexes. Finally, we compare time-balanced andsize-balanced time-based partitioning schemes. The experimentalresults at small to medium number of processors reveal that formedium to long length queries time-based partitioning works better.
Doküman numaralarını yeniden atama yolu ile ters indeks sıkıştırma
Compression of inverted indexes received great attention in recent years. An inverted index consists of lists of document identifiers, also referred as posting lists, for each term. Compressing an inverted index reduces the size of the index, which also improves the query performance due to the reduction on disk access times.In recent studies, it is shown that reassigning document identifiers has great effect in compression of an inverted index. In this work, we propose a noveltechnique that reassigns both term and document identifiers of an inverted index by transforming the matrix representation of the index into a block-diagonal form, which improves the compression ratio dramatically. We adapted row-net hypergraph-partitioning model for the transformation into block-diagonal form, which improves the compression ratio by as much as 50%. To the best of our knowledge, this method performs more effectively than previous inverted index compression techniques.