More Like this

1. SF-GRASS: solver-free graph spectral sparsification

   https://doi.org/10.1145/3400302.3415629  

   Zhang, Ying; Zhao, Zhiqiang; Feng, Zhuo (November 2020, International Conference on Computer-Aided Design)

   null (Ed.)

   Recent spectral graph sparsification techniques have shown promising performance in accelerating many numerical and graph algorithms, such as iterative methods for solving large sparse matrices, spectral partitioning of undirected graphs, vectorless verification of power/thermal grids, representation learning of large graphs, etc. However, prior spectral graph sparsification methods rely on fast Laplacian matrix solvers that are usually challenging to implement in practice. This work, for the first time, introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing (GSP) techniques. We introduce a local spectral embedding scheme for efficiently identifying spectrally-critical edges that are key to preserving graph spectral properties, such as the first few Laplacian eigenvalues and eigenvectors. Since the key kernel functions in SF-GRASS can be efficiently implemented using sparse-matrix-vector-multiplications (SpMVs), the proposed spectral approach is simple to implement and inherently parallel friendly. Our extensive experimental results show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks when compared with prior state-of-the-art spectral methods. 

   more » « less
2. Alternate routes to mnm ⁵ s ² U synthesis in Gram-positive bacteria

   https://doi.org/10.1128/jb.00452-23  

   Jaroch, Marshall; Sun, Guangxin; Tsui, Ho-Ching Tiffany; Reed, Colbie; Sun, Jingjing; Jörg, Marko; Winkler, Malcolm E; Rice, Kelly C; Dziergowska, Agnieszka; Stich, Troy A; et al (April 2024, Journal of Bacteriology)

   Henkin, Tina M (Ed.)

   The wobble bases of tRNAs that decode split codons are often heavily modified. In bacteria, tRNA^{Glu, Gln, Asp}contains a variety of xnm⁵s²U derivatives. The synthesis pathway for these modifications is complex and fully elucidated only in a handful of organisms, including the Gram-negativeEscherichia coliK12 model. Despite the ubiquitous presence of mnm⁵s²U modification, genomic analysis shows the absence ofmnmCorthologous genes, suggesting the occurrence of alternate biosynthetic schemes for the conversion of cmnm⁵s²U to mnm⁵s²U. Using a combination of comparative genomics and genetic studies, a member of the YtqA subgroup of the radical Sam superfamily was found to be involved in the synthesis of mnm⁵s²U in bothBacillus subtilisandStreptococcus mutans. This protein, renamed MnmL, is encoded in an operon with the recently discovered MnmM methylase involved in the methylation of the pathway intermediate nm⁵s²U into mnm⁵s²U inB. subtilis. Analysis of tRNA modifications of bothS. mutansandStreptococcus pneumoniaeshows that growth conditions and genetic backgrounds influence the ratios of pathway intermediates owing to regulatory loops that are not yet understood. The MnmLM pathway is widespread along the bacterial tree, with some phyla, such as Bacilli, relying exclusively on these two enzymes. Although mechanistic details of these newly discovered components are not fully resolved, the occurrence of fusion proteins, alternate arrangements of biosynthetic components, and loss of biosynthetic branches provide examples of biosynthetic diversity to retain a conserved tRNA modification in Nature.IMPORTANCEThe xnm⁵s²U modifications found in several tRNAs at the wobble base position are widespread in bacteria where they have an important role in decoding efficiency and accuracy. This work identifies a novel enzyme (MnmL) that is a member of a subgroup of the very versatile radical SAM superfamily and is involved in the synthesis of mnm⁵s²U in several Gram-positive bacteria, including human pathogens. This is another novel example of a non-orthologous displacement in the field of tRNA modification synthesis, showing how different solutions evolve to retain U34 tRNA modifications. 

   more » « less
3. HESSLE-FREE: He terogeneou s S ystems Le veraging F uzzy Control for R untim e Resourc e Management

   https://doi.org/10.1145/3358203  

   Moazzemi, Kasra; Maity, Biswadip; Yi, Saehanseul; Rahmani, Amir M.; Dutt, Nikil (October 2019, ACM Transactions on Embedded Computing Systems)
4. SAGE: S tealthy A ttack Ge neration in cyber-physical systems

   https://doi.org/10.1080/24725854.2023.2184004  

   Biehler, Michael; Zhong, Zhen; Shi, Jianjun (January 2023, IISE Transactions)

   Cyber-physical systems (CPS) have been increasingly attacked by hackers. CPS are especially vulnerable to attackers that have full knowledge of the system's configuration. Therefore, novel anomaly detection algorithms in the presence of a knowledgeable adversary need to be developed. However, this research is still in its infancy due to limited attack data availability and test beds. By proposing a holistic attack modeling framework, we aim to show the vulnerability of existing detection algorithms and provide a basis for novel sensor-based cyber-attack detection. Stealthy Attack GEneration (SAGE) for CPS serves as a tool for cyber-risk assessment of existing systems and detection algorithms for practitioners and researchers alike. Stealthy attacks are characterized by malicious injections into the CPS through input, output, or both, which produce bounded changes in the detection residue. By using the SAGE framework, we generate stealthy attacks to achieve three objectives: (i) Maximize damage, (ii) Avoid detection, and (iii) Minimize the attack cost. Additionally, an attacker needs to adhere to the physical principles in a CPS (objective iv). The goal of SAGE is to model worst-case attacks, where we assume limited information asymmetries between attackers and defenders (e.g., insider knowledge of the attacker). Those worst-case attacks are the hardest to detect, but common in practice and allow understanding of the maximum conceivable damage. We propose an efficient solution procedure for the novel SAGE optimization problem. The SAGE framework is illustrated in three case studies. Those case studies serve as modeling guidelines for the development of novel attack detection algorithms and comprehensive cyber-physical risk assessment of CPS. The results show that SAGE attacks can cause severe damage to a CPS, while only changing the input control signals minimally. This avoids detection and keeps the cost of an attack low. This highlights the need for more advanced detection algorithms and novel research in cyber-physical security. 

   more » « less
5. ASA: A ccelerating S parse A ccumulation in Column-wise SpGEMM

   https://doi.org/10.1145/3543068  

   Zhang, Chao; Bremer, Maximilian; Chan, Cy; Shalf, John; Guo, Xiaochen (December 2022, ACM Transactions on Architecture and Code Optimization)

   Sparse linear algebra is an important kernel in many different applications. Among various sparse general matrix-matrix multiplication (SpGEMM) algorithms, Gustavson’s column-wise SpGEMM has good locality when reading input matrix and can be easily parallelized by distributing the computation of different columns of an output matrix to different processors. However, the sparse accumulation (SPA) step in column-wise SpGEMM, which merges partial sums from each of the multiplications by the row indices, is still a performance bottleneck. The state-of-the-art software implementation uses a hash table for partial sum search in the SPA, which makes SPA the largest contributor to the execution time of SpGEMM. There are three reasons that cause the SPA to become the bottleneck: (1) hash probing requires data-dependent branches that are difficult for a branch predictor to predict correctly; (2) the accumulation of partial sum is dependent on the results of the hash probing, which makes it difficult to hide the hash probing latency; and (3) hash collision requires time-consuming linear search and optimizations to reduce these collisions require an accurate estimation of the number of non-zeros in each column of the output matrix. This work proposes ASA architecture to accelerate the SPA. ASA overcomes the challenges of SPA by (1) executing the partial sum search and accumulate with a single instruction through ISA extension to eliminate data-dependent branches in hash probing, (2) using a dedicated on-chip cache to perform the search and accumulation in a pipelined fashion, (3) relying on the parallel search capability of a set-associative cache to reduce search latency, and (4) delaying the merging of overflowed entries. As a result, ASA achieves an average of 2.25× and 5.05× speedup as compared to the state-of-the-art software implementation of a Markov clustering application and its SpGEMM kernel, respectively. As compared to a state-of-the-art hashing accelerator design, ASA achieves an average of 1.95× speedup in the SpGEMM kernel. 

   more » « less