Various complexities involved in organizing and assessing computer science (CS) capstone programs are well-documented. We explore how student learning can be improved by studying the role of instructors and external industry professionals (''clients'') as project mentors in a two-semester capstone program. Three mentoring models are studied: the instructor mentors teams in both semesters (I-I), a client is the mentor in both semesters (C-C), and a hybrid model where the mentor is the instructor in the first semester and a client in the second semester (I-C). The study included 287 unique participants in a two-semester capstone sequence (574 total observations) across three academic years at Washington State University, a public university. Collected data included aggregated grade values for assessing individual student performance in a course, student evaluations of a course, and self-rated student perceptions regarding their own career readiness. Analysis of the data indicated that the hybrid (I-C) mentoring model produced higher values in the course performance and career readiness categories. Qualitative data in the form of anonymous student comments are discussed. The study's implications and possible limitations for replication are highlighted.

Computing educators face many challenges when teaching capstone courses. We examine what impact capstone project type has on student performance, career readiness and course evaluation by considering three project types: Academic, Industry, and Service Learning. We studied data from 139 unique participants, each for two semesters (total 278 observations), over three years of a capstone program at Washington State University. We studied data for individual student performance in the course, student evaluation of the course, and self-rated student perceptions regarding career readiness. Analysis of data indicated that Industry projects with a full-stack application resulted in higher values for course evaluations and career readiness scores. Ranked & pairwise correlation analyses were conducted, revealing pairwise correlations between career readiness and course evaluations (strong-negative) and student performance and course evaluations (moderate-negative); possible implications are discussed. Qualitative data in the form of anonymous student comments via course evaluation surveys indicate some students appreciated working on business-grade applications while other students found amount of documentation involved excessive. The study's implications and possible limitations for replication are addressed, including capstone program length, cohort size, project recruitment, and project variance.

Evaluating machine learning models is crucial not only for determining their technical accuracy but also for assessing their potential societal implications. While the potential for low-sample-size bias in algorithms is well known, we demonstrate the significance of sample-size bias induced by combinatorics in classification metrics. This revelation challenges the efficacy of these metrics in assessing bias with high resolution, especially when comparing groups of disparate sizes, which frequently arise in social applications. We provide analyses of the bias that appears in several commonly applied metrics and propose a model-agnostic assessment and correction technique. Additionally, we analyze counts of undefined cases in metric calculations, which can lead to misleading evaluations if improperly handled. This work illuminates the previously unrecognized challenge of combinatorics and probability in standard evaluation practices and thereby advances approaches for performing fair and trustworthy classification methods.

The lack of high-quality cyber security data is a significant barrier to the development of intrusion detection systems (IDSs). A growing body of work has shown that generative AI models provide an intuitive solution to this problem through the creation of synthetic samples of the minority classes within existing datasets. However, transforming IDS datasets into feature vectors usable with generative models is a steep challenge. Additionally, the research bridging generative models and IDS datasets has not kept pace with recent advancements in generative models. This paper addresses both of these issues with respect to network intrusion detection data specifically. In a novel approach, we use a very recent innovation in generative models known as Denoising Diffusion Implicit Models (DDIMs) to produce a hybrid synthetic/real dataset. We then evaluate its performance compared to prior work on the original dataset and compared against an approach based on Variational AutoEncoder (VAE). Our results demonstrate significant improvement in several IDS metrics when the IDS is trained on synthetic data from either model. The evaluation also highlights that the DDIM performs similarly or better than the VAE, depending on the IDS used in testing. Furthermore, we explore three different feature encoding strategies—normalized, binary, and decimal—in our evaluations and find that binary encoding has the highest performance for the NetFlow dataset NF-UQ-NIDS that we studied.

The rapid evolution of modern electric power distribution systems into complex networks of interconnected active devices, distributed generation (DG), and storage poses increasing difficulties for system operators. The large-scale integration of distributed energy resources (DERs) and the rapid exchange of measurement data via communication networks present major opportunities for advancing grid operations but also introduce greater uncertainty, higher data dimensionality, more complex network and device models, and challenging control and optimization problems. Deep reinforcement learning (DRL) algorithms are promising in addressing these challenges. However, they have not been effectively adapted for power systems applications, requiring extensive customization for implementation and evaluation. This has resulted in reproducibility challenges and a steep learning curve for researchers new to applying DRL algorithms to the power systems domain. To bridge these gaps, this tutorial aims to serve as a valuable resource for researchers interested in exploring learning-based algorithms to operate active power distribution networks. Specifically, this work presents a generalized process for translating sequential decision-making problems in power distribution systems into Markov decision process (MDP) formulations, illustrated through concrete grid service examples. Additionally, we introduce a simple environment design strategy to develop and evaluate example DRL algorithms for distribution system applications, complete with an included code repository to guide users through environment construction.

The k -dimensional Weisfeiler-Lehman ( k -WL) algorithm—developed as an efficient heuristic for testing if two graphs are isomorphic—is a fundamental kernel for node embedding in the emerging field of graph neural networks. Unfortunately, the k -WL algorithm has exponential storage requirements, limiting the size of graphs that can be handled. This work presents a novel k -WL scheme with a storage requirement orders of magnitude lower while maintaining the same accuracy as the original k -WL algorithm. Due to the reduced storage requirement, our scheme allows for processing much bigger graphs than previously possible on a single compute node. For even bigger graphs, we provide the first distributed-memory implementation. Our k -WL scheme also has significantly reduced communication volume and offers high scalability. Our experimental results demonstrate that our approach is significantly faster and has superior scalability compared to five other implementations employing state-of-the-art techniques.

Leveraging current legal standards, we define bias through the lens of marginal benefits and objective testing with the novel metric "Objective Fairness Index". This index combines the contextual nuances of objective testing with metric stability, providing a legally consistent and reliable measure. Utilizing the Objective Fairness Index, we provide fresh insights into sensitive machine learning applications, such as COMPAS (recidivism prediction), highlighting the metric's practical and theoretical significance. The Objective Fairness Index allows one to differentiate between discriminatory tests and systemic disparities.

This work examines the state-of-the-art of cybersecurity education in the United States by considering two sources of data. The first source consists of Programs of Study for cybersecurity programs at Centers of Academic Excellence in Cybersecurity designated by the National Security Agency. Statistics were aggregated from a sample of one hundred CAE-C institutions, trends and gaps are identified, and improvements are proposed. The second source is peer-reviewed research published in the field of cybersecurity education over the last decade. A review of this literature shows a strong focus on identifying instructional content and developing educational tools while simultaneously indicating a shortage of research into rigorous evaluation of the instructional approaches being used to teach cybersecurity. Our review of these two sources of data highlight two paths to improving cybersecurity education in the United States. First, institutions offering cybersecurity degrees could work more closely with groups such as NIST, ACM, and IEEE to ensure their curricula match the needs of industry and they are graduating work-ready cybersecurity specialists. While CAE-C designation provides certain requirements for the amount of cybersecurity content included in curricula, designated institutions vary widely in the types of programs they offer and how many cybersecurity-specific courses they provide. Second, cybersecurity education could benefit from an influx of ideas from educational psychology regarding instructional theories such as cognitive load theory.

Hypergraphs offer flexible and robust data representations for many applications, but methods that work directly on hypergraphs are not readily available and tend to be prohibitively expensive. Much of the current analysis of hypergraphs relies on first performing a graph expansion – either based on the nodes (clique expansion), or on the hyperedges (line graph) − and then running standard graph analytics on the resulting representative graph. However, this approach suffers from massive space complexity and high computational cost with increasing hypergraph size. Here, we present efficient, parallel algorithms to accelerate and reduce the memory footprint of higher-order graph expansions of hypergraphs. Our results focus on the hyperedge-based s-line graph expansion, but the methods we develop work for higher-order clique expansions as well. To the best of our knowledge, ours is the first framework to enable hypergraph spectral analysis of a large dataset on a single shared-memory machine. Our methods enable the analysis of datasets from many domains that previous graph-expansion-based models are unable to provide. The proposed s-line graph computation algorithms are orders of magnitude faster than state-of-the-art sparse general matrix-matrix multiplication methods, and obtain approximately 2–31× speedup over a prior state-of-the-art heuristic-based algorithm for$s$-line graph computation.

Parallel scientific applications can benefit from decoupling communication and synchronization. One-sided programming abstractions, which separate communication from synchronization, have in fact served as a motivation for partitioned global address space (PGAS) models. However, the use of PGAS models in application codes in a manner that fully exploits the benefit of these programming models requires significant development effort. Meanwhile, a vast majority of scientific codes already use the Message Passing Interface (MPI) and need convenient features to support application-specific one-sided communication scenarios. MPI Remote Memory Access (RMA) can be employed for this purpose. MPI is a low-level API, however, and developing applications with MPI RMA requires programmers to be well versed in its nuances. We present RMACXX, a compact set of C++ bindings to MPI-3 RMA, to ease the use of MPI RMA. Unlike other PGAS models, which may have interoperability issues with MPI, RMACXX is written on top of MPI and uses the same runtime as MPI. The basic functionality of RMACXX adds only a relatively small number of extra instructions (about 20) to the critical communication path. Moreover, RMACXX provides an intuitive API for building a wide variety of scientific applications while enjoying performance matching handwritten MPI-3 RMA codes.

This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hyper-graphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected if there is at least one common “neighbor”. However, minimal commonality sometimes discards the “strength” of connections and interactions among groups. To this end, considering the “width” of a connection, referred to as the s-overlap of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, s-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the s-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute s-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the s-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than 10x) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large$s$value).

A significant amount of distributed photovoltaic (PV) generation is “invisible” to distribution system operators since it is behind the meter on customer premises and not directly monitored by the utility. The generation essentially adds an unknown varying negative demand to the system, which causes additional uncertainty in determining the total load. This uncertainty directly impacts system reliability, cold load pickup, load behavior modeling, and hence cost of operation. Thus, it is essential to create low-complexity localized models for estimating power generation from these invisible sites behind the meters. This article proposes an adaptive machine learning framework to: a) learn using weather data and a minimal number of BTM PV generation measurement sensors, b) forecast PV generation using weather, location of PV, and trained ML model at location for unmeasured BTM PV; c) use estimated PV and net load measured by smart meter or smart transformer to estimate total true load at each time step; and d) learn the specific load patterns eventually to adapt localized models. The proposed framework's core idea is to transform the data such that: a) the machine learning model can effectively utilize the time dependency of measurements; and b) the measurements are transformed into a lower dimensional space to reduce complexity while maintaining accuracy. The transformed measurements are then used to train the machine learning models for load/PV disaggregation. Machine learning models investigated include linear regression, decision tree, random forest (RF), and multilayer perceptron. The proposed framework's efficacy is demonstrated using two datasets, a real dataset from Hawaii and a simulated dataset using detailed models in GridLab-D. Several test/training split scenarios, including 90-10% split, one-month-out, one-season-out, and panel-independent split are presented to provide a thorough evaluation of the proposed framework. Results on both datasets show that the proposed framework can estimate PV generation with high accuracy using low-complexity methods. The accuracy results are comparable to higher complexity models (e.g., deep architectures), and RF is found to provide superior performance with these specific datasets compared to the other ML models investigated.

Label Propagation, while more commonly known as a machine learning algorithm for classification, is also an effective method for detecting communities in networks. We propose a new Direction Optimizing Label Propagation Algorithm (DOLPA) that relies on the use of frontiers and alternates between label push and label pull operations to enhance the performance of the standard Label Propagation Algorithm (LPA). Specifically, DOLPA has parameters for tuning the processing order of vertices in a graph, which in turn reduces the number of edges visited and improves the quality of solution obtained. We apply DOLPA to the community detection problem, present the design and implementation of the algorithm, and discuss its shared-memory parallelization using OpenMP. Empirically, we evaluate our algorithm using synthetic graphs as well as real-world networks. Compared with the state-of-the-art Parallel Label Propagation algorithm, we achieve at least two times the F-Score while reducing the runtime by 50% for synthetic graphs with overlapping communities. We also compare DOLPA against state of the art parallel implementation of the Louvain method using the same graphs and show that DOLPA achieves about three times the F-Score at 10% the runtime.

Machine learning algorithms, which form the core intelligence of wearables, traditionally deduce a computational model from a set of training data to detect events of interest. However, in the dynamic environment in which wearables operate, the accuracy of a computational model drops whenever changes in configuration or context of the system occur. In this paper, using transfer learning as an organizing principle, we propose a novel design framework to enable autonomous reconfiguration of wearable systems. More specifically, we focus on the cases where the specifications of sensor(s) or the subject vary compared to what is available in the training data. We develop two new algorithms for data mapping (the mapping is between the training data and the data for the current operating setting). The first data mapping algorithm combines effective methods for finding signal similarity with network-based clustering, while the second algorithm is based on finding signal motifs. The data mapping algorithms constitute the centerpiece of the transfer learning phase in our framework. We demonstrate the efficacy of the data mapping algorithms using two publicly available datasets on human activity recognition. We show that the data mapping algorithms are up to two orders of magnitude faster compared to a brute-force approach. We also show that the proposed framework overall improves activity recognition accuracy by up to 15 percent for the first dataset and by up to 32 percent for the second dataset.

Traditional implementations of parallel graph operations on distributed memory platforms are written using Message Passing Interface (MPI) point-to-point communication primitives such as Send-Recv (blocking and nonblocking). Apart from this classical model, the MPI community has over the years added other communication models; however, their suitability for handling the irregular traffic workloads typical of graph operations remain comparatively less explored. Our aim in this paper is to study these relatively underutilized communication models of MPI for graph applications. More specifically, we evaluate MPI's one-sided programming, or Remote Memory Access (RMA), and nearest neighborhood collectives using a process graph topology. There are features in these newer models that are intended to better map to irregular communication patterns, as exemplified in graph algorithms. As a concrete application for our case study, we use distributed memory implementations of an approximate weighted graph matching algorithm to investigate performances of MPI3 RMA and neighborhood collective operations compared to nonblocking Send-Recv. A matching in a graph is a subset of edges such that no two matched edges are incident on the same vertex. A maximum weight matching is a matching of maximum weight computed as the sum of the weights of matched edges. Execution of graph matching is dominated by high volume of irregular memory accesses, making it an ideal candidate for studying the effects of various MPI communication models on graph applications at scale. Our neighborhood collectives and RMA implementations yield up to 6× speedup over traditional nonblocking Send-Recv implementations on thousands of cores of the NERSC Cori supercomputer. We believe the lessons learned from this study can be adopted to benefit a wider range of graph applications.

Data is increasingly being used to make everyday life easier and better. Applications such as waiting time estimation, traffic prediction, and parking search are good examples of how data from different sources can be used to facilitate our daily life. In this study, we consider an under-utilized data source: university ID cards. Such cards are used on many campuses to purchase food, allow access to different areas, and even take attendance in classes. In this article, we use data from our university to analyze usage of the university fitness center and build a predictor for future visit volume. The work makes several contributions: it demonstrates the richness of the data source, shows how the data can be leveraged to improve student services, discovers interesting trends and behavior, and serves as a case study illustrating the entire data science process.

In most real-world networks, the nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters, such that nodes within a community are more likely to be "related" to one another than they are to the rest of the network. The goodness of partitioning into communities is typically measured using a well known measure called modularity. However, modularity optimization is an NP-complete problem. In 2008, Blondel, et al. introduced a multi-phase, iterative heuristic for modularity optimization, called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. In this paper, we present the design of a distributed memory implementation of the Louvain algorithm for parallel community detection. Our approach begins with an arbitrarily partitioned distributed graph input, and employs several heuristics to speedup the computation of the different steps of the Louvain algorithm. We evaluate our implementation and its different variants using real-world networks from various application domains (including internet, biology, social networks). Our MPI+OpenMP implementation yields about 7x speedup (on 4K processes) for soc-friendster network (1.8B edges) over a state-of-the-art shared memory multicore implementation (on 64 threads), without compromising output quality. Furthermore, our distributed implementation was able to process a larger graph (uk-2007; 3.3B edges) in 32 seconds on 1K cores (64 nodes) of NERSC Cori, when the state-of-the-art shared memory implementation failed to run due to insufficient memory on a single Cori node containing 128 GB of memory.

BACKGROUND: Sequence similarity networks are useful for classifying and characterizing biologically important proteins. Threshold-based approaches to similarity network construction using exact distance measures are prohibitively slow to compute and rely on the difficult task of selecting an appropriate threshold, while similarity networks based on approximate distance calculations compromise useful structural information. RESULTS: We present an alternative network representation for a set of sequence data that overcomes these drawbacks. In our model, called the Directed Weighted All Nearest Neighbors (DiWANN) network, each sequence is represented by a node and is connected via a directed edge to only the closest sequence, or sequences in the case of ties, in the dataset. Our contributions span several aspects. Specifically, we: (i) Apply an all nearest neighbors network model to protein sequence data from three different applications and examine the structural properties of the networks; (ii) Compare the model against threshold-based networks to validate their semantic equivalence, and demonstrate the relative advantages the model offers; (iii) Demonstrate the model's resilience to missing sequences; and (iv) Develop an efficient algorithm for constructing a DiWANN network from a set of sequences. We find that the DiWANN network representation attains similar semantic properties to threshold-based graphs, while avoiding weaknesses of both high and low threshold graphs. Additionally, we find that approximate distance networks, using BLAST bitscores in place of exact edit distances, can cause significant loss of structural information. We show that the proposed DiWANN network construction algorithm provides a fourfold speedup over a standard threshold based approach to network construction. We also identify a relationship between the centrality of a sequence in a similarity network of an Anaplasma marginale short sequence repeat dataset and how broadly that sequence is dispersed geographically. CONCLUSION: We demonstrate that using approximate distance measures to rapidly construct similarity networks may lead to significant deficiencies in the structure of that network in terms centrality and clustering analyses. We present a new network representation that maintains the structural semantics of threshold-based networks while increasing connectedness, and an algorithm for constructing the network using exact distance measures in a fraction of the time it would take to build a threshold-based equivalent.

Human activity recognition (HAR) plays a central role in health-care, fitness and sport applications because of its potential to enable context-aware human monitoring. With the increase in popularity of wearable devices, we are witnessing a large influx in availability of human activity data. For effective analysis and interpretation of these heterogeneous and high-volume streaming data, we need powerful algorithms. In particular, there is a strong need for developing algorithms for robust classification of human activity data that specifically address challenges associated with dynamic environments (e.g. different users, signal heterogeneity). We use the term robust here in two, orthogonal senses: 1) leveraging related data in such a way that knowledge is transferred to a new context; and 2) actively reconfiguring machine learning algorithms such that they can be applied in a new context. In this paper, we propose an architecture that combines an active learning approach with a novel deep network. Our deep neural network exploits both Convolutional and Long Short-Term Memory (LSTM) layers in order to learn hierarchical representation of features and capture time dependencies from raw-data. The active learning process allows us to choose the best instances for fine-tuning the deep network to the new setting in which the system operates (i.e. a new subject). We demonstrate the efficacy of the architecture using real data of human activity. We show that the accuracy of activity recognition reaches over 90% by annotating less than 20% of unlabeled data.

Graph coloring-in a generic sense-is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to here as balanced coloring. In this paper, we consider balanced coloring models in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring for two variants of coloring problem, distance-1 coloring (the standard coloring problem) and partial distance-2 coloring (defined on a bipartite graph). We present parallelization approaches for multi-core and manycore architectures and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application-viz. parallel community detection, which is an example of an irregular application. In addition, we propose several extensions to our basic balancing schemes and evaluate their balancing efficacy and performance characteristics. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring.

Wearables have emerged as a revolutionary technology in many application domains including healthcare and fitness. Machine learning algorithms, which form the core intelligence of wearables, traditionally deduce a computational model from a set of training examples to detect events of interest (e.g. activity type). However, in the dynamic environment in which wearables typically operate in, the accuracy of a computational model drops whenever changes in configuration of the system (such as device type and sensor orientation) occur. Therefore, there is a need to develop systems which can adapt to the new configuration autonomously. In this paper, using transfer learning as an organizing principle, we develop several algorithms for data mapping. The data mapping algorithms employ effective signal similarity methods and are used to adapt the system to the new configuration. We demonstrate the efficacy of the data mapping algorithms using a publicly available dataset on human activity recognition.

We study effective parallelization of approximation algorithms for the one-dimensional bin packing problem on a multicore platform. Bin packing is a classic combinatorial optimization problem that aims to pack a given sequence of items into a minimum number of equal-sized bins. The problem potentially serves as a model for a wide variety of applications. Examples include: packing data into chunks in a memory hierarchy in a given system to increase application performance, loading vehicles subject to weight limitations, and packing TV commercials into station breaks. Bin packing has long served as a proving ground for the analysis of approximation algorithms and played a crucial role in the development of much of the theory of approximation algorithms. Its parallelization, however, has received comparatively much less attention. In this work, we develop multiple parallel versions of an effective approximation algorithm (First Fit Decreasing) for the problem and investigate the trade-off between solution quality and execution time. We use OpenMP and Cilk Plus as mechanisms for achieving the parallelization. The new parallel algorithms obtain a speedup of more than 10× (on 32 cores) for moderate to large input sequences without sacrificing much on the quality of solution produced by the sequential algorithm - in particular, we see only about 3 to 30% increase in the number of bins compared to the sequential version. In turn, the solution obtained by the sequential First Fit Decreasing algorithm is provably almost optimal (the approximation ratio is less than 1.3).

A one-sided programming model separates communication from synchronization, and is the driving principle behind partitioned global address space (PGAS) libraries such as Global Arrays (GA) and SHMEM. PGAS models expose a rich set of functionality that a developer needs in order to implement mathematical algorithms that require frequent multidimensional array accesses. However, use of existing PGAS libraries in application codes often requires significant development effort in order to fully exploit these programming models. On the other hand, a vast majority of scientific codes use MPI either directly or indirectly via third-party scientific computation libraries, and need features to support application-specific communication requirements (e.g., asynchronous update of distributed sparse matrices, commonly arising in machine learning workloads). For such codes it is often impractical to completely shift programming models in favor of special one-sided communication middleware. Instead, an elegant and productive solution is to exploit the one-sided functionality already offered by MPI-3 RMA (Remote Memory Access). We designed a general one-sided interface using the MPI-3 passive RMA model for remote matrix operations in the linear algebra library Elemental, we call the interface we designed RMAInterface. Elemental is an open source library for distributed-memory dense and sparse linear algebra and optimization. We employ RMAInterface to construct a Global Arrays-like API and demonstrate its performance scalability and competitivity with that of the existing GA (with ARMCI-MPI) for a quantum chemistry application.

Graph colouring is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional colouring heuristics aim to reduce the number of colours used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable colouring is a theoretical formulation of colouring that guarantees a perfect balance among color classes, and its practical relaxation is referred to as balanced colouring. In this paper, we revisit the problem of balanced colouring in the context of parallel computing. The goal is to achieve a balanced colouring of an input graph without increasing the number of colours that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced colouring, present parallelization approaches for multi-core and manicure architectures, and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced colouring heuristics on a concrete application - viz. parallel community detection, which is an example of an irregular application. The thorough treatment of balanced colouring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using colouring.

We present a suite of fast and effective algorithms, encapsulated in a software package called ColPack, for a variety of graph coloring and related problems. Many of the coloring problems model partitioning needs arising in compression-based computation of Jacobian and Hessian matrices using Algorithmic Differentiation. Several of the coloring problems also find important applications in many areas outside derivative computation, including frequency assignment in wireless networks, scheduling, facility location, and concurrency discovery and data movement operations in parallel and distributed computing. The presentation in this article includes a high-level description of the various coloring algorithms within a common design framework, a detailed treatment of the theory and efficient implementation of known as well as new vertex ordering techniques upon which the coloring algorithms rely, a discussion of the package's software design, and an illustration of its usage. The article also includes an extensive experimental study of the major algorithms in the package using real-world as well as synthetically generated graphs.

The computation of a sparse Hessian matrix H using automatic differentiation (AD) can be made efficient using the following four-step procedure: (1) Determine the sparsity structure of H, (2) obtain a seed matrix S that defines a column partition of H using a specialized coloring on the adjacency graph of H, (3) compute the compressed Hessian matrix B ≡ HS, and (4) recover the numerical values of the entries of H from B. The coloring variant used in the second step depends on whether the recovery in the fourth step is direct or indirect: a direct method uses star coloring and an indirect method uses acyclic coloring. In an earlier work, we had designed and implemented effective heuristic algorithms for these two NP-hard coloring problems. Recently, we integrated part of the developed software with the AD tool ADOL-C, which has recently acquired a sparsity detection capability. In this paper, we provide a detailed description and analysis of the recovery algorithms and experimentally demonstrate the efficacy of the coloring techniques in the overall process of computing the Hessian of a given function using ADOL-C as an example of an AD tool. We also present new analytical results on star and acyclic coloring of chordal graphs. The experimental results show that sparsity exploitation via coloring yields enormous savings in runtime and makes the computation of Hessians of very large size feasible. The results also show that evaluating a Hessian via an indirect method is often faster than a direct evaluation. This speedup is achieved without compromising numerical accuracy.

Finding a good graph coloring quickly is often a crucial phase in the development of efficient, parallel algorithms for many scientific and engineering applications. In this paper we consider the problem of solving the graph coloring problem itself in parallel. We present a simple and fast parallel graph coloring heuristic that is well suited for shared memory programming and yields an almost linear speedup on the PRAM model. We also present a second heuristic that improves on the number of colors used. The heuristics have been implemented using OpenMP. Experiments conducted on an SGI Cray Origin 2000 supercomputer using very large graphs from finite element methods and eigenvalue computations validate the theoretical run-time analysis. Copyright © 2000 John Wiley & Sons, Ltd.