143 results on '"Kaya, Kamer"'
Search Results
2. A hybrid CPU–GPU solver based on three-dimensional spectral Chebyshev technique for determining the dynamic behavior of thick sandwich panels
- Author
-
Rafiei Anamagh, Mirmeysam, Gokalp, Kaya, Akyıldız, Taha Atahan, Alan, Salih, Kaya, Kamer, and Bediz, Bekir
- Published
- 2023
- Full Text
- View/download PDF
3. Scaling matrices and counting the perfect matchings in graphs
- Author
-
Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, and Uçar, Bora
- Published
- 2022
- Full Text
- View/download PDF
4. Synchronizing billion-scale automata
- Author
-
Taş, Mustafa Kemal, Kaya, Kamer, and Yenigün, Hüsnü
- Published
- 2021
- Full Text
- View/download PDF
5. Boosting expensive synchronizing heuristics
- Author
-
Saraç, N. Ege, Altun, Ömer Faruk, Atam, Kamil Tolga, Karahoda, Sertaç, Kaya, Kamer, and Yenigün, Hüsnü
- Published
- 2021
- Full Text
- View/download PDF
6. Multicore and manycore parallelization of cheap synchronizing sequence heuristics
- Author
-
Karahoda, Sertaç, Erenay, Osman Tufan, Kaya, Kamer, Türker, Uraz Cengiz, and Yenigün, Hüsnü
- Published
- 2020
- Full Text
- View/download PDF
7. Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices
- Author
-
Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, and Uçar, Bora
- Published
- 2018
- Full Text
- View/download PDF
8. Determination of Pancreatic Beta Cell Reserve in Antidepressant Users and Evaluation of Its Relationship with Metabolic Parameters: A Cross-Sectional Study.
- Author
-
KAYA, Kamer, GÜROK, Mehmet Gürkan, KILINÇ, Faruk, ÜSTÜNDAĞ, Bilal, ÖRÜM, Mehmet Hamdi, and ATMACA, Murad
- Subjects
PANCREATIC beta cells ,ANTIDEPRESSANTS ,METABOLISM ,INSULIN resistance ,BIOCHEMISTRY - Abstract
Copyright of Firat Universitesi Sağlik Bilimleri Tip Dergisi is the property of Firat Universitesiu, Saglik Bilimleri Enstitusu and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 2024
9. Synchronizing heuristics: Speeding up the fastest
- Author
-
Karahoda, Sertaç, Kaya, Kamer, and Yenigün, Hüsnü
- Published
- 2018
- Full Text
- View/download PDF
10. A framework for parallel second order incremental optimization algorithms for solving partially separable problems
- Author
-
Kaya, Kamer, Öztoprak, Figen, Birbil, Ş. İlker, Cemgil, A. Taylan, Şimşekli, Umut, Kuru, Nurdan, Koptagel, Hazal, and Öztürk, M. Kaan
- Published
- 2019
- Full Text
- View/download PDF
11. Architectural Aspects of Genocide
- Author
-
KAYA, KAMER ASLI, SOYLUK, ASENA, and İLERİSOY, ZEYNEP YEŞİM
- Published
- 2023
12. Two approximation algorithms for bipartite matching on multicore architectures
- Author
-
Dufossé, Fanny, Kaya, Kamer, and Uçar, Bora
- Published
- 2015
- Full Text
- View/download PDF
13. Incremental closeness centrality in distributed memory
- Author
-
Sarıyüce, Ahmet Erdem, Saule, Erik, Kaya, Kamer, and Çatalyürek, Ümit V.
- Published
- 2015
- Full Text
- View/download PDF
14. Hypergraph partitioning for multiple communication cost metrics: Model and methods
- Author
-
Deveci, Mehmet, Kaya, Kamer, Uçar, Bora, and Çatalyürek, Ümit V.
- Published
- 2015
- Full Text
- View/download PDF
15. Regularizing graph centrality computations
- Author
-
Sarıyüce, Ahmet Erdem, Saule, Erik, Kaya, Kamer, and Çatalyürek, Ümit V.
- Published
- 2015
- Full Text
- View/download PDF
16. Sharing DSS by the Chinese Remainder Theorem
- Author
-
Kaya, Kamer and Selçuk, Ali Aydın
- Published
- 2014
- Full Text
- View/download PDF
17. Special issue on High‐Performance Computing Conference (BASARIM 2022).
- Author
-
Kaya, Kamer, Şener, Cevat, and Yenigün, Hüsnü
- Subjects
CONFERENCES & conventions - Abstract
Summary: This is an editorial for the Special Issue on the 7th High‐Performance Computing Conference (BAŞARIM 2022) organized on May 11–13, 2022, at Sabanci University Altunizade Digital Campus, İstanbul. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
18. Push-relabel based algorithms for the maximum transversal problem
- Author
-
Kaya, Kamer, Langguth, Johannes, Manne, Fredrik, and Uçar, Bora
- Published
- 2013
- Full Text
- View/download PDF
19. Boosting Graph Embedding on a Single GPU.
- Author
-
Aljundi, Amro Alabsi, Akyildiz, Taha Atahan, and Kaya, Kamer
- Subjects
GRAPH algorithms ,MACHINE learning ,GRAPHICS processing units ,CLASSIFICATION algorithms ,CHARTS, diagrams, etc. - Abstract
Graphs are ubiquitous, and they can model unique characteristics and complex relations of real-life systems. Although using machine learning (ML) on graphs is promising, their raw representation is not suitable for ML algorithms. Graph embedding represents each node of a graph as a $d$ d -dimensional vector which is more suitable for ML tasks. However, the embedding process is expensive, and CPU-based tools do not scale to real-world graphs. In this work, we present GOSH, a GPU-based tool for embedding large-scale graphs with minimum hardware constraints. GOSH employs a novel graph coarsening algorithm to enhance the impact of updates and minimize the work for embedding. It also incorporates a decomposition schema that enables any arbitrarily large graph to be embedded with a single GPU. As a result, GOSH sets a new state-of-the-art in link prediction both in accuracy and speed, and delivers high-quality embeddings for node classification at a fraction of the time compared to the state-of-the-art. For instance, it can embed a graph with over 65 million vertices and 1.8 billion edges in less than 30 minutes on a single GPU. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
20. Fast recommendation on bibliographic networks with sparse-matrix ordering and partitioning
- Author
-
Küçüktunç, Onur, Kaya, Kamer, Saule, Erik, and Çatalyürek, Ümit V.
- Published
- 2013
- Full Text
- View/download PDF
21. Efficient broadcast encryption with user profiles
- Author
-
Ak, Murat, Kaya, Kamer, Onarlıoğlu, Kaan, and Selçuk, Ali Aydın
- Published
- 2010
- Full Text
- View/download PDF
22. Optimal subset-difference broadcast encryption with free riders
- Author
-
Ak, Murat, Kaya, Kamer, and Selçuk, Ali Aydın
- Published
- 2009
- Full Text
- View/download PDF
23. Merging network patterns: a general framework to summarize biomedical network data
- Author
-
Xiang, Yang, Fuhry, David, Kaya, Kamer, Jin, Ruoming, Çatalyürek, Ümit V., and Huang, Kun
- Published
- 2012
- Full Text
- View/download PDF
24. Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories
- Author
-
Kaya, Kamer, Uçar, Bora, and Aykanat, Cevdet
- Published
- 2007
- Full Text
- View/download PDF
25. Threshold cryptography based on Asmuth–Bloom secret sharing
- Author
-
Kaya, Kamer and Selçuk, Ali Aydın
- Published
- 2007
- Full Text
- View/download PDF
26. Iterative-improvement-based heuristics for adaptive scheduling of tasks sharing files on heterogeneous master-slave environments
- Author
-
Kaya, Kamer and Aykanat, Cevdet
- Subjects
Iterative methods (Mathematics) -- Analysis ,Task analysis -- Methods ,Heuristic programming -- Methods ,Business ,Computers ,Electronics ,Electronics and electrical industries - Abstract
The problem of scheduling independent but file-sharing tasks on heterogeneous master-slave platforms is investigated and a three-phase scheduling approach involving initial task assignment, refinement and execution ordering phases is proposed. The results show that the proposed three-phase scheduling approach works much better than the existing one.
- Published
- 2006
27. Machine learning‐based load distribution and balancing in heterogeneous database management systems.
- Author
-
Abdennebi, Anes, Elakaş, Anıl, Taşyaran, Fatih, Öztürk, Erdinç, Kaya, Kamer, and Yıldırım, Sinan
- Subjects
DATABASES ,LOADERS (Machines) ,RANDOM forest algorithms ,TASK analysis ,CENTRAL processing units ,GRAPHICS processing units ,ONLINE data processing - Abstract
Summary: For dynamic and continuous data analysis, conventional OLTP systems are slow in performance. Today's cutting‐edge high‐performance computing hardware, such as GPUs, has been used as accelerators for data analysis tasks, which traditionally leverage CPUs on classical database management systems (DBMS). When CPUs and GPUs are used together, the architectural heterogeneity, that is, leveraging hardware with different performance characteristics jointly, creates complex problems that need careful treatment for performance optimization. Load distribution and balancing are crucial problems for DBMSs working on heterogeneous architectures. In this work, focusing on a hybrid, CPU‐GPU database management system to process users' queries, we propose heuristical and machine‐learning‐based (ML‐based) load distribution and balancing models. In more detail, we employ multiple linear regression (MLR), random forest (RF), and Adaboost (Ada) models to dynamically decide the processing unit for each incoming query based on the response time predictions on both CPU and GPU. The ML‐based models outperformed the other algorithms, as well as the CPU and GPU‐only running modes with up to 27%, 29%, and 40%, respectively, in overall performance (response time) while answering intense real‐life working scenarios. Finally, we propose to use a hybrid load‐balancing model that would be more efficient than the models we tested in this work. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
28. Task assignment in heterogeneous computing systems
- Author
-
Ucar, Bora, Aykanat, Cevdet, Kaya, Kamer, and Ikinci, Murat
- Published
- 2006
- Full Text
- View/download PDF
29. Effective heuristics for matchings in hypergraphs
- Author
-
Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, Uçar, Bora, Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Inria Grenoble Rhône-Alpes
- Subjects
Tensor scaling ,Karp- Sipser heuristic ,Heuristique Karp–Sipser ,Couplage ,Matching in hypergraphs ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Hypergraphes ,[INFO]Computer Science [cs] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,d-dimensional matching - Abstract
The problem of finding a maximum cardinality matching in a d-partite d-uniform hypergraph is an important problem in combinatorial optimization and has beentheoretically analyzed by several researchers. In this work, we first devise heuristics for this problem by generalizing the existing cheap graph matching heuristics. Then, we propose a novel heuristic based on tensor scaling to extend the matching via judicious hyperedge selections. Experiments on random, synthetic and real-life hypergraphs show that this new heuristic is highly practical and superior to the others on finding a matching with largecardinality.; Le problème consistant à trouver un couplage maximal dans un hypergraphe uniforme ayant d parts est un problème important en optimisation combinatoire. Dans ce travail, nous concevons d’abord des heuristiques pour ce problème en généralisant les heuristiques de couplage dans des graphes. Ensuite, nous proposons une nouvelle heuristique basée sur des méthodes de mise à l’échelle de tenseur pour étendre le couplage via des sélections judicieuses d’hyperarêtes. Des expériences sur des hypergraphes aléatoires, synthétiques et réels montrent que cette nouvelle heuristique est simple à mettre en pratique et supérieure aux autres pour trouver des couplages de grande cardinalité.
- Published
- 2018
30. Boosting Parallel Influence-Maximization Kernels for Undirected Networks With Fusing and Vectorization.
- Author
-
Gokturk, Gokhan and Kaya, Kamer
- Subjects
- *
GRAPH algorithms , *ALGORITHMS , *APPROXIMATION algorithms , *SOCIAL networks , *KERNEL functions , *LANGEVIN equations - Abstract
Influence maximization (IM) is the problem of finding a seed vertex set which is expected to incur the maximum influence spread on a graph. It has various applications in practice such as devising an effective and efficient approach to disseminate information, news or ad within a social network. The problem is shown to be NP-hard and approximation algorithms with provable quality guarantees exist in the literature. However, these algorithms are computationally expensive even for medium-scaled graphs. Furthermore, graph algorithms usually suffer from spatial and temporal irregularities during memory accesses, and this adds an extra cost on top of the already expensive IM kernels. In this article we leverage fused sampling, memoization, and vectorization to restructure, parallelize and boost their performance on undirected networks. The proposed approach employs a pseudo-random function and performs multiple Monte-Carlo simulations in parallel to exploit the SIMD lanes effectively and efficiently. In addition, it significantly reduces the number of edge traversals, hence the amount of data brought from the memory, which is critical for almost all memory-bound graph kernels. We apply the proposed approach to the traditional MixGreedy algorithm and propose INFuseR-MG which is more than $3000\times$ 3000 × faster than the greedy approaches and can run on large graphs that have been considered as too large in the literature. For instance, the new algorithm runs in 2.09, 0.08, 0.36 seconds on graphs Amazon, NetHEP, NetPhy with 16 threads where the sequential baseline takes 141.3, 259.1 and 1725.2 seconds, respectively. To compare INFuseR-MG with the state-of-the-art approximation algorithms, we conduct a thorough experimental analysis with various influence settings. The results on real-life, undirected networks show that on 16 threads, INFuseR-MG is $2.3\times$ 2. 3 × – $173.8\times$ 173. 8 × faster than state-of-the-art while being superior in terms of influence scores, and using a comparable amount of memory. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
31. GOSH: Embedding Big Graphs on Small Hardware.
- Author
-
Akyildiz, Taha Atahan, Aljundi, Amro Alabsi, and Kaya, Kamer
- Published
- 2020
- Full Text
- View/download PDF
32. Scaling matrices and counting the perfect matchings in graphs
- Author
-
Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, Uçar, Bora, Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Inria Grenoble Rhône-Alpes
- Subjects
matrices bistochastiques ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory ,Permanent approximation ,algorithmes randomisés ,randomized algorithms ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Sinkhorn-Knopp scaling ,doubly stochastic matrices ,permanent - Abstract
We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.; Nous étudions des méthodes randomiséese efficaces pour approximer le nombre de couplages parfaits dans des graphes bipartis et des graphes généraux. Notre approche se base sur l'assignation de probabilités aux arêtes.
- Published
- 2018
33. Normalisation de matrice et dénombrement des couplages parfaits dans les graphes
- Author
-
Dufossé, Fanny, Kaya, Kamer, Panagiotas, Ioannis, Uçar, Bora, Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), and Inria Grenoble Rhône-Alpes
- Subjects
matrices bistochastiques ,ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory ,Permanent approximation ,algorithmes randomisés ,randomized algorithms ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Sinkhorn-Knopp scaling ,doubly stochastic matrices ,permanent - Abstract
We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.; Nous étudions des méthodes randomiséese efficaces pour approximer le nombre de couplages parfaits dans des graphes bipartis et des graphes généraux. Notre approche se base sur l'assignation de probabilités aux arêtes.
- Published
- 2018
34. Acyclic partitioning of large directed acyclic graphs
- Author
-
Herrmann, Julien, Yusuf Özkaya, M, Uçar, Bora, Kaya, Kamer, Çatalyürek, Ümit, School of Computational Science and Engineering, Georgia Institute of Technology [Atlanta], Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Faculty of Engineering and Natural Sciences (Sabanci University), Sabanci University [Istanbul], and Inria - Research Centre Grenoble – Rhône-Alpes
- Subjects
acyclic partitioning ,multilevel partitioning ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,directed graph ,partitionnement acyclic ,partitionnement multiniveau ,graphes orientés - Abstract
We investigate the problem of partitioning the vertices of a directed acyclic graph into a given number of parts. The objective function is to minimize the number or the total weight of the edges having end points in different parts, which is also known as edge cut. The standard load balancing constraint of having an equitable partition of the vertices among the parts should be met.Furthermore, the partition is required to be {\em acyclic}, i.e., the inter-part edges between the vertices from different parts should preserve an acyclic dependency structure among the parts. In this work, we adopt the multilevel approach with coarsening, initial partitioning, and refinementphases for acyclic partitioning of directed acyclic graphs. We focus on two-way partitioning (sometimes called bisection), as this scheme can be used in a recursive way for multi-way partitioning. To ensure the acyclicity of the partition at all times, we propose novel and efficient coarsening andrefinement heuristics. The quality of the computed acyclic partitions is assessed by computing the edge cut. We also propose effective ways to use the standard undirected graph partitioning methods in our multilevel scheme. We perform a large set of experiments on a dataset consisting of (i)~graphs coming from an application and (ii)~some others corresponding to matrices from a public collection. We report improvements, on average, around 59\% compared to the current state of the art.; Nous étudions le problème du partitionnement des sommets d’un graphe acyclique dirigé en un nombre donné de parties. La fonction objectiveest de minimiser le poids total des arêtes ayant des extrémités dans différentes parties, qui sont également nommées arêtes coupées. La contrainted’équilibrage de charge standard d’avoir une partition équitable des sommets entre les parties doit être respectée. En outre, la partition doit être acyclique, c’est-à-dire, les arêtes coupées doivent préserver une structure de dépendance acyclique entre les parties. Dans ce travail, nous adoptons une approche multiniveaux avec des étapes de contraction, partitionnement initial et raffinement pour le partitionnement acyclique des graphes acycliques dirigés. Nous nous concentrons sur la bissection, car ce schéma peut être utilisé d’une manière récursive pour le partitionnement multi-voies. Pour assurer l’acyclicité du partitionnement à tout moment, nous proposons des méthodes de contraction etde raffinement. La qualité des partitions acycliques calculées est évaluée en calculant la somme des poids des arêtes coupées. Nous proposons également des moyens efficaces afin d’utiliser des méthodes standard de partitionnement de graphes non orientés dans notre schéma multi-niveaux. Nous effectuons un grand nombre d’expériences sur un ensemble de données constitué de (i) graphes provenant d’une application, et (ii) d’autres graphes correspondant à des matrices d’une collection publique. Nous rapportons des améliorations par rapport aux méthodes existantes d’environ 59 % en moyenne.
- Published
- 2018
35. Reordering matrices for optimal sparse matrix bipartitioning
- Author
-
Mumcuyan, Aras, Kaya, Kamer, and Yenigün, Hüsnü
- Subjects
QA075 Electronic computers. Computer science - Abstract
Sparse-matrix vector multiplication (SpMV) is one of the widely used and extensively studied kernels in today’s scientific computing and high-performance computing domains. The efficiency and scalability of this kernel is extensively investigated on single-core, multi-core, many-core processors and accelerators, and on distributed memory. In general, a good mapping of an application’s tasks to the processing units in a distributed environment is important since communication among these tasks is the main bottleneck on scalability. A fundamental approach to solve this problem is modeling the application via a graph/hypergraph and partitioning it. For SpMV, several graph/hypergraph models have been proposed. These approaches consider the problem as a balanced partitioning problem where the vertices (tasks) are partitioned (assigned) to the parts (processors) in a way that the total vertex weight (processor load) is balanced and the total communication incurred among the processors is minimized. The partitioning problem is NP-Hard and all the existing studies and tools use heuristics to solve the problem. For graphs, the literature on optimal partitioning contains a number of notable studies; however for hypergraphs, very little work has been done. Unfortunately, it has been shown that unlike graphs, hypergraphs can exactly model the total communication for SpMV. Recently, Pelt and Bisseling proposed a novel, purely combinatorial branch-and-bound-based approach for the sparse-matrix bipartitioning problem which can tackle relatively larger hypergraphs that were impossible to optimally partition into two by using previous methods. This work can be considered as an extension to their approach with two ideas. We propose to use; 1) matrix ordering techniques to use more information in the earlier branches of the tree, and 2) a machine learning approach to choose the best ordering based on matrix features. As our experiments on various matrices will show, these enhancements make the optimal bipartitioning process much faster.
- Published
- 2017
36. Multi-exponentiations on multi-cores
- Author
-
Topçuoğlu, Cem, Kaya, Kamer, and Savaş, Erkay
- Subjects
QA075 Electronic computers. Computer science - Abstract
Modular exponentiation lies at the core of many cryptographic schemes and its efficient implementation is a must for a reasonable practical performance. For various applications, multiple exponentiations with different bases and exponents need to be performed and multiplied. Although this multiexponentiation operation can be implemented by individually exponentiating the bases to their corresponding exponents, as discussed in the literature, a significant performance boost can be obtained when the operation is considered as a whole. However, performing separate exponentiations is pleasingly parallelizable but the latter approach requires a careful implementation on a multi-core processor. In this work, we propose a parallel algorithm and implementation based on an existing multi-exponentiation algorithm with precomputation. The experimental results show that the proposed implementation is significantly faster than the existing parallel multi-exponentiation schemes in the literature.
- Published
- 2017
37. HAMSI: A parallel incremental optimization algorithm using quadratic approximations for solving partially separable problems
- Author
-
Kaya, Kamer, Öztoprak, Figen, Birbil, Ş. İlker, Cemgil, A. Taylan, Şimşekli, Umut, Kuru, Nurdan, Koptagel, Hazal, and Öztürk, M. Kaan
- Subjects
FOS: Computer and information sciences ,Computer Science - Learning ,QA075 Electronic computers. Computer science ,Statistics - Machine Learning ,Machine Learning (stat.ML) ,Machine Learning (cs.LG) - Abstract
We propose HAMSI (Hessian Approximated Multiple Subsets Iteration), which is a provably convergent, second order incremental algorithm for solving large-scale partially separable optimization problems. The algorithm is based on a local quadratic approximation, and hence, allows incorporating curvature information to speed-up the convergence. HAMSI is inherently parallel and it scales nicely with the number of processors. Combined with techniques for effectively utilizing modern parallel computer architectures, we illustrate that the proposed method converges more rapidly than a parallel stochastic gradient descent when both methods are used to solve large-scale matrix factorization problems. This performance gain comes only at the expense of using memory that scales linearly with the total size of the optimization variables. We conclude that HAMSI may be considered as a viable alternative in many large scale problems, where first order methods based on variants of stochastic gradient descent are applicable., Comment: The software is available at https://github.com/spartensor/hamsi-mf
- Published
- 2017
38. Parallelized preconditioned model building algorithm for matrix factorization
- Author
-
Kaya, Kamer, Birbil, İlker, Öztürk, Mehmet Kaan, and Gohari, Amir
- Subjects
QA075 Electronic computers. Computer science - Abstract
Matrix factorization is a common task underlying several machine learning applications such as recommender systems, topic modeling, or compressed sensing. Given a large and possibly sparse matrix A, we seek two smaller matrices W and H such that their product is as close to A as possible. The objective is minimizing the sum of square errors in the approximation. Typically such problems involve hundreds of thousands of unknowns, so an optimizer must be exceptionally efficient. In this study, a new algorithm, Preconditioned Model Building is adapted to factorize matrices composed of movie ratings in the MovieLens data sets with 1, 10, and 20 million entries. We present experiments that compare the sequential MATLAB implementation of the PMB algorithm with other algorithms in the minFunc package. We also employ a lock-free sparse matrix factorization algorithm and provide a scalable shared-memory parallel implementation. We show that (a) the optimization performance of the PMB algorithm is comparable to the best algorithms in common use, and (b) the computational performance can be significantly increased with parallelization
- Published
- 2017
39. A CRT-based verifiable secret sharing scheme secure against unbounded adversaries
- Author
-
Ersoy, Oguzhan, Pedersen, Thomas Brochmann, Kaya, Kamer, Selcuk, Ali Aydin, Anarim, Emin, TOBB ETU, Faculty of Engineering, Department of Computer Engineering, TOBB ETÜ, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, and Selçuk, Ali Aydın
- Subjects
TheoryofComputation_MISCELLANEOUS ,QA075 Electronic computers. Computer science ,Joint Random Secret Sharing ,Verifiable Secret Sharing ,Statistically Hiding Commitments ,Asmuth-Bloom ,Chinese Remainder Theorem - Abstract
For commitments on secrets, statistical hiding is a must when we are dealing with a long-term secret or when the secret domain is small enough for a brute-force attack by a powerful adversary. Unfortunately, all the Chinese Remainder Theorem-based verifiable secret sharing schemes in the literature are either insecure or suffer from the vulnerability of computationally hiding commitments. To the best of our knowledge, there exist five such studies where two of them were already proven to be insecure. In this work, we first show that two of the remaining schemes are also insecure, that is, the schemes reveal information on the secret even when the adversary is passive. In addition, the remaining one is only secure against a computationally bounded adversary which can be a problem for secret sharing schemes requiring long-term secret obscurity or using small secret domain. We propose a modification for the latter scheme and prove that the modified scheme is a secure verifiable secret sharing scheme against an unbounded adversary. Lastly, as an application, we show how to use the new scheme for joint random secret sharing and analyze the practicality and efficiency of the proposed schemes. Copyright (C) 2016 John Wiley & Sons, Ltd.
- Published
- 2016
40. Parallel algorithms for computing sparse matrix permanents.
- Author
-
KAYA, Kamer
- Subjects
- *
SPARSE matrices , *PARALLEL algorithms , *PARALLEL programming , *SHIP captains - Abstract
The permanent is an important characteristic of a matrix and it has been used in many applications. Unfortunately, it is a hard to compute and hard to approximate the immanant. For dense/full matrices, the fastest exact algorithm, Ryser, has O(2n-1n complexity. In this work, a parallel algorithm, SkipPer, is proposed to exploit the sparsity within the input matrix as much as possible. SkipPer restructures the matrix to reduce the overall work, skips the unnecessary steps, and employs a coarse-grain, shared-memory parallelization with dynamic scheduling. The experiments show that SkipPer increases the performance of exact permanent computation up to 140x compared to the naive version for general matrices. Furthermore, thanks to the coarse-grain parallelization, 14-15x speedup on average is obtained with β = 16 threads over sequential SkipPer. Overall, by exploiting the sparsity and parallelism, the speedup is 2000x for some of the matrices used in the experimental setting. The proposed techniques in this paper can be used to significantly improve the performance of exact permanent computation by simply replacing Ryser with SkipPer, especially when the matrix is highly sparse. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
41. Multilevel Threshold Secret and Function Sharing based on the Chinese Remainder Theorem
- Author
-
Ersoy, Oguzhan, Kaya, Kamer, and Kaskaloglu, Kerem
- Subjects
FOS: Computer and information sciences ,Computer Science - Cryptography and Security ,Cryptography and Security (cs.CR) - Abstract
A recent work of Harn and Fuyou presents the first multilevel (disjunctive) threshold secret sharing scheme based on the Chinese Remainder Theorem. In this work, we first show that the proposed method is not secure and also fails to work with a certain natural setting of the threshold values on compartments. We then propose a secure scheme that works for all threshold settings. In this scheme, we employ a refined version of Asmuth-Bloom secret sharing with a special and generic Asmuth-Bloom sequence called the {\it anchor sequence}. Based on this idea, we also propose the first multilevel conjunctive threshold secret sharing scheme based on the Chinese Remainder Theorem. Lastly, we discuss how the proposed schemes can be used for multilevel threshold function sharing by employing it in a threshold RSA cryptosystem as an example.
- Published
- 2016
42. Hypergraph partitioning for multiple communication cost metrics: model and methods
- Author
-
Deveci, Mehmet, Kaya, Kamer, Uçar, Bora, and Çatalyürek, Ümit V.
- Subjects
QA075 Electronic computers. Computer science - Abstract
We investigate hypergraph partitioning-based methods for efficient parallelization of communicating tasks. A good partitioning method should divide the load among the processors as evenly as possible and minimize the inter-processor communication overhead. The total communication volume is the most popular communication overhead metric which is reduced by the existing state-of-the-art hypergraph partitioners. However, other metrics such as the total number of messages, the maximum amount of data transferred by a processor, or a combination of them are equally, if not more, important. Existing hypergraph-based solutions use a two phase approach to minimize such metrics where in each phase, they minimize a different metric, sometimes at the expense of others. We propose a one-phase approach where all the communication cost metrics can be effectively minimized in a multi-objective setting and reductions can be achieved for all metrics together. For an accurate modeling of the maximum volume and the number of messages sent and received by a processor, we propose the use of directed hypergraphs. The directions on hyperedges necessitate revisiting the standard partitioning heuristics. We do so and propose a multi-objective, multi-level hypergraph partitioner called UMPa. The partitioner takes various prioritized communication metrics into account, and optimizes all of them together in the same phase. Compared to the state-of-the-art methods which only minimize the total communication volume, we show on a large number of problem instances that UMPa produces better partitions in terms of several communication metrics.
- Published
- 2014
43. Incremental closeness centrality in distributed memory
- Author
-
Sarıyüce, Ahmet Erdem, Saule, Erik, Kaya, Kamer, and Çatalyürek, Ümit V.
- Subjects
QA075 Electronic computers. Computer science - Abstract
Networks are commonly used to model traffic patterns, social interactions, or web pages. The vertices in a network do not possess the same characteristics: some vertices are naturally more connected and some vertices can be more important. Closeness centrality (CC) is a global metric that quantifies how important is a given vertex in the network. When the network is dynamic and keeps changing, the relative importance of the vertices also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose Streamer, a distributed memory framework for incrementally maintaining the closeness centrality scores of a network upon changes. It leverages pipelined, replicated parallelism, and SpMM-based BFSs, and it takes NUMA effects into account. It makes maintaining the Closeness Centrality values of real-life networks with millions of interactions significantly faster and obtains almost linear speedups on a 64 nodes 8 threads/node cluster.
- Published
- 2014
44. MULTILEVEL ALGORITHMS FOR ACYCLIC PARTITIONING OF DIRECTED ACYCLIC GRAPHS.
- Author
-
HERRMANN, JULIEN, YUSUF ÖZKAYA, M., UÇAR, BORA, KAYA, KAMER, and ÇATALYÜREK, ÜMIT V.
- Subjects
DIRECTED acyclic graphs ,PARALLEL algorithms ,UNDIRECTED graphs ,PHASE partition ,DIRECTED graphs ,PARTITION functions ,GEOMETRIC vertices - Abstract
We investigate the problem of partitioning the vertices of a directed acyclic graph into a given number of parts. The objective function is to minimize the number or the total weight of the edges having end points in different parts, which is also known as the edge cut. The standard load balancing constraint of having an equitable partition of the vertices among the parts should be met. Furthermore, the partition is required to be acyclic; i.e., the interpart edges between the vertices from different parts should preserve an acyclic dependency structure among the parts. In this work, we adopt the multilevel approach with coarsening, initial partitioning, and refinement phases for acyclic partitioning of directed acyclic graphs. We focus on two-way partitioning (sometimes called bisection), as this scheme can be used in a recursive way for multiway partitioning. To ensure the acyclicity of the partition at all times, we propose novel and efficient coarsening and refinement heuristics. The quality of the computed acyclic partitions is assessed by computing the edge cut. We also propose effective ways to use the standard undirected graph partitioning methods in our multilevel scheme. We perform a large set of experiments on a dataset consisting of (i) graphs coming from an application and (ii) some others corresponding to matrices from a public collection. We report significant improvements compared to the current state of the art. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
45. Multilevel Threshold Secret Sharing using the Chinese Remainder Theorem.
- Author
-
Ersoy, Oğuzhan, Kaya, Kamer, and Kaşkaloğlu, Kerem
- Subjects
- *
CHINESE remainder theorem , *CRYPTOSYSTEMS , *SHARING - Abstract
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 CRT-based 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. [ABSTRACT FROM AUTHOR]
- Published
- 2019
46. Foreword: 1st International Workshop on High Performance Computing for Big Data
- Author
-
Kaya, Kamer, Gedik, Buğra, and Çatalyürek, Ümit V.
- Subjects
International workshops ,Big data ,High performance computing (HPC) ,Parallel processing ,Technical presentations ,High performance computing ,Data problems - Abstract
Date of Conference: 9-12 Sept. 2014 Conference name: 43rd International Conference on Parallel Processing Workshops, 2014 The 1st International Workshop on High Performance Computing for Big Data (HPC4BD) is held on September 10, 2014 in concordance with 43rd International Conference on Parallel Processing (ICPP-2014). The workshop aimed to bring high performance computing (HPC) experts and experts from various application domains together to discuss their Big Data problems. There were four works accepted to be presented in this year's workshop. This foreword presents a summary of the them. © 2014 IEEE.
- Published
- 2014
47. On analysis of partitioning models and metrics in parallel sparse matrix-vector multiplication
- Author
-
Catalyurek, Umit, Kaya, Kamer, Uçar, Bora, Department of Biomedical Informatics [Columbus], Ohio State University [Columbus] (OSU), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
hypergraph partitioning ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Parallel sparse-matrix vector multiplication - Abstract
Graph/hypergraph partitioning models and methods have been successfully used to minimize the communication requirements among processors in several parallel computing applications. Parallel sparse matrix-vector multiplication~(SpMxV) is one of the representative applications that renders these models and methods indispensable in many scientific computing contexts. We investigate the interplay of several partitioning metrics and execution times of SpMxV implementations in three libraries: Trilinos, PETSc, and an in-house one. We design and carry out experiments with up to 512 processors and investigate the results with regression analysis. Our experiments show that the partitioning metrics, although not an exact measure of communication cost, influence the performance greatly in a distributed memory setting. The regression analyses demonstrate which metric is the most influential for the execution time of the three libraries used.
- Published
- 2013
48. Incremental Algorithms for Network Management and Analysis based on Closeness Centrality
- Author
-
Sariyuce, Ahmet Erdem, Kaya, Kamer, Saule, Erik, and Catalyurek, Umit V.
- Subjects
FOS: Computer and information sciences ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) - Abstract
Analyzing networks requires complex algorithms to extract meaningful information. Centrality metrics have shown to be correlated with the importance and loads of the nodes in network traffic. Here, we are interested in the problem of centrality-based network management. The problem has many applications such as verifying the robustness of the networks and controlling or improving the entity dissemination. It can be defined as finding a small set of topological network modifications which yield a desired closeness centrality configuration. As a fundamental building block to tackle that problem, we propose incremental algorithms which efficiently update the closeness centrality values upon changes in network topology, i.e., edge insertions and deletions. Our algorithms are proven to be efficient on many real-life networks, especially on small-world networks, which have a small diameter and a spike-shaped shortest distance distribution. In addition to closeness centrality, they can also be a great arsenal for the shortest-path-based management and analysis of the networks. We experimentally validate the efficiency of our algorithms on large networks and show that they update the closeness centrality values of the temporal DBLP-coauthorship network of 1.2 million users 460 times faster than it would take to compute them from scratch. To the best of our knowledge, this is the first work which can yield practical large-scale network management based on closeness centrality values.
- Published
- 2013
49. Investigations on push-relabel based algorithms for the maximum transversal problem
- Author
-
Kaya, Kamer, Langguth, Johannes, Manne, Fredrik, Uçar, Bora, Department of Biomedical Informatics [Columbus], Ohio State University [Columbus] (OSU), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,[INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS] - Abstract
We investigate the push-relabel algorithm for solving the problem of finding a maximum cardinality matching in a bipartite graph in the context of the maximum transversal problem. We describe in detail an optimized yet easy-to-implement version of the algorithm and fine-tune its parameters. We also introduce new performance-enhancing techniques. On a wide range of real-world instances, we compare the push-relabel algorithm with state-of-the-art augmenting path-based algorithms and the recently proposed pseudoflow approach. We conclude that a carefully tuned push-relabel algorithm is competitive with all known augmenting path-based algorithms, and superior to the pseudoflow-based ones.; Nous étudions le problème de couplage maximum dans des graphes bipartis. Nous décrivons en détail une version optimisée de l'algorithme en ajustant ses paramètres. L'algorithme est facile à mettre en œuvre. Nous introduisons également de nouvelles techniques pour améliorer la performance de l'algorithme. Sur un large éventail de cas du monde réel, nous comparons l'algorithme Push-Relabel avec des algorithmes basés sur les concepts de chemins augmentants et de pseudoflot récemment proposés. Nous concluons qu'un algorithme de type Push-Relabel soigneusement réglé est en concurrence avec tous les algorithmes connus de type chemins augmentants, et supérieur à ceux de type pseudoflot.
- Published
- 2012
50. Shattering and Compressing Networks for Centrality Analysis
- Author
-
Sar��y��ce, Ahmet Erdem, Saule, Erik, Kaya, Kamer, and ��ataly��rek, ��mit V.
- Subjects
Social and Information Networks (cs.SI) ,FOS: Computer and information sciences ,Physics - Physics and Society ,Computer Science - Data Structures and Algorithms ,FOS: Physical sciences ,Data Structures and Algorithms (cs.DS) ,Computer Science - Social and Information Networks ,Physics and Society (physics.soc-ph) - Abstract
Who is more important in a network? Who controls the flow between the nodes or whose contribution is significant for connections? Centrality metrics play an important role while answering these questions. The betweenness metric is useful for network analysis and implemented in various tools. Since it is one of the most computationally expensive kernels in graph mining, several techniques have been proposed for fast computation of betweenness centrality. In this work, we propose and investigate techniques which compress a network and shatter it into pieces so that the rest of the computation can be handled independently for each piece. Although we designed and tuned the shattering process for betweenness, it can be adapted for other centrality metrics in a straightforward manner. Experimental results show that the proposed techniques can be a great arsenal to reduce the centrality computation time for various types of networks.
- Published
- 2012
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.