Institute of Computing and Cybersystems (ICC) Blog

Category: SAS

Ali Ebnenasir is Co-Author of Publication in ACM Transactions on Computational Logic

Published
Ali Ebnenasir

An article co-authored by Ali Ebnenasir (SAS/CS) and Alex Klinkhamer, “Verification of Livelock-Freedom and Self-Stabilization on Parameterized Rings,” was recently published in ACM Transactions on Computational Logic.

Abstract: This article investigates the verification of livelock-freedom and self-stabilization on parameterized rings consisting of symmetric, constant space, deterministic, and self-disabling processes. The results of this article have a significant impact on several fields, including scalable distributed systems, resilient and self-* systems, and verification of parameterized systems. First, we identify necessary and sufficient local conditions for the existence of global livelocks in parameterized unidirectional rings with unbounded (but finite) number of processes under the interleaving semantics. Using a reduction from the periodic domino problem, we show that, in general, verifying livelock-freedom of parameterized unidirectional rings is undecidable (specifically, Π10-complete) even for constant space, deterministic, and self-disabling processes. This result implies that verifying self-stabilization for parameterized rings of self-disabling processes is also undecidable. We also show that verifying livelock-freedom and self-stabilization remain undecidable under (1) synchronous execution semantics, (2) the FIFO consistency model, and (3) any scheduling policy. We then present a new scope-based method for detecting and constructing livelocks in parameterized rings. The proposed semi-algorithm behind our scope-based verification is based on a novel paradigm for the detection of livelocks that totally circumvents state space exploration. Our experimental results on an implementation of the proposed semi-algorithm are very promising as we have found livelocks in parameterized rings in a few microseconds on a regular laptop. The results of this article have significant implications for scalable distributed systems with cyclic topologies.

https://dl.acm.org/citation.cfm?id=3326456&dl=ACM&coll=DL

doi: 10.1145/3326456

Continue Reading →

Scalable Spectral Sparsification of Graph Laplacians and Integrated Circuits

Published
Circuit board

Researcher: Zhuo Feng, Associate Professor, Electrical and Computer Engineering

Sponsor: National Science Foundation: SHF: Small

Amount of Support: $450,000

Duration of Support: 3 years

Abstract: This research is motivated by investigations on scalable methods for design simplifications of nanoscale integrated circuits (ICs). This is to be achieved by extending the associated spectral graph sparsification framework to handle Laplacian-like matrices derived from general nonlinear IC modeling and simulation problems. The results from this research may prove to be key to the development of highly scalable computer-aided design algorithms for modeling, simulation, design, optimization, as well as verification of future nanoscale ICs that can easily involve multi-billions of circuit components. The algorithms and methodologies developed will be disseminated to leading technology companies that may include semiconductor and Electronic Design Automation companies as well as social and network companies, for potential industrial deployments.

Spectral graph sparsification aims to find an ultra-sparse subgraph (a.k.a. sparsifier) such that its Laplacian can well approximate the original one in terms of its eigenvalues and eigenvectors. Since spectrally similar subgraphs can approximately preserve the distances, much faster numerical and graph-based algorithms can be developed based on these “spectrally” sparsified networks. A nearly-linear complexity spectral graph sparsification algorithm is to be developed based on a spectral perturbation approach. The proposed method is highly scalable and thus can be immediately leveraged for the development of nearly-linear time sparse matrix solvers and spectral graph (data) partitioning (clustering) algorithms for large real-world graph problems in general. The results of the research may also influence a broad range of computer science and engineering problems related to complex system/network modeling, numerical linear algebra, optimization, machine learning, computational fluid dynamics, transportation and social networks, etc.

More details.

Continue Reading →

Improving Reliability of In-Memory Storage

Published
Electronic circuit board

Researcher: Jianhui Yue, PI, Assistant Professor, Computer Science

Sponsor: National Science Foundation, SHF: Small: Collaborative Research

Amount of Support: $192, 716

Duration of Support: 3 years

Abstract: Emerging nonvolatile memory (NVM) technologies, such as PCM, STT-RAM, and memristors, provide not only byte-addressability, low-latency reads and writes comparable to DRAM, but also persistent writes and potentially large storage capacity like an SSD. These advantages make NVM likely to be next-generation fast persistent storage for massive data, referred to as in-memory storage. Yet, NVM-based storage has two challenges: (1) Memory cells have limited write endurance (i.e., the total number of program/erase cycles per cell); (2) NVM has to remain in a consistent state in the event of a system crash or power loss. The goal of this project is to develop an efficient in-memory storage framework that addresses these two challenges. This project will take a holistic approach, spanning from low-level architecture design to high-level OS management, to optimize the reliability, performance, and manageability of in-memory storage. The technical approach will involve understanding the implication and impact of the write endurance issue when cutting-edge NVM is adopted into storage systems. The improved understanding will motivate and aid the design of cost-effective methods to improve the life-time of in-memory storage and to achieve efficient and reliable consistence maintenance.

Publications:

Pai Chen, Jianhui Yue, Xiaofei Liao, Hai Jin. “Optimizing DRAM Cache by a Trade-off between Hit Rate and Hit Latency,” IEEE Transactions on Emerging Topics in Computing, 2018. doi:10.1109/TETC.2018.2800721

Chenlei Tang, Jiguang Wan, Yifeng Zhu, Zhiyuan Liu, Peng Xu, Fei Wu and Changsheng Xie. “RAFS: A RAID-Aware File System to Reduce Parity Update Overhead for SSD RAID,” Design Automation Test In Europe Conference (DATE) 2019, 2019.

Pai Chen, Jianhui Yue, Xiaofei Liao, Hai Jin. “Trade-off between Hit Rate and Hit Latency for Optimizing DRAM Cache,” IEEE Transactions on Emerging Topics in Computing, 2018.

More details

Continue Reading →

Zhou Feng is PI on $500K NSF Project

Published

Zhuo Feng (ECE/ICC) is Principal Investigator on a project that has received a $500,000 research and development grant from the National Science Foundation. This potential three-year project is titled, “SHF: Small: Spectral Reduction of Large Graphs and Circuit Networks.”

This research project will investigate a truly-scalable yet unified spectral graph reduction approach that allows reducing large-scale, real-world directed and undirected graphs with guaranteed preservation of the original graph spectra. Unlike prior methods that are only suitable for handling specific types of graphs (e.g. undirected or strongly-connected graphs), this project uses a more universal approach and thus will allow for spectral reduction of a much wider range of real-world graphs that may involve billions of elements:

  • spectrally-reduced social (data) networks allow for more efficiently modeling, mining and analysis of large social (data) networks;
  • spectrally-reduced neural networks allow for more scalable model training and processing in emerging machine learning tasks;
  • spectrally-reduced web-graphs allow for much faster computations of personalized PageRank vectors;
  • spectrally-reduced integrated circuit networks will lead to more efficient partitioning, modeling, simulation, optimization and verification of large chip designs, etc.

From Tech Today, June 21, 2019

Continue Reading →

Soner Onder To Present Invited Talk

Published

Soner OnderDr. Soner Onder (CS, SAS) will present an invited talk titled “Program semantics meets architecture: What if we did not have branches?” at a workshop organized in honor of the 80th birthday of Prof. Yale Patt of University of Texas, Austin. Prof. Patt is a prominent researcher with decades of accomplishments in Computer Architecture.

The workshop, titled “Yale:80 in 2019, Pushing the Envelope of Computing for the Future,” will take place July 1-2, 2019, in Barcelona, Spain. The workshop is organized by Universitat Politècnica de Catalunya and Barcelona Supercomputing Center, and sponsored by the Ministry of Science, Innovation and Universities of Spain, among others.

Continue Reading →

ICC Members Receive Achievement Awards at Annual Banquet

Published

Soner Onder, Bo Chen, Kevin TrewarthaAt the annual awards banquet of the Michigan Tech Institute of Computing and Cybersysytems (ICC), on Friday, April 12, three ICC members received the ICC Achievement Award in recognition of their exceptional contributions to research and learning in the fields of computing.

Soner Önder, director of the ICC Center for Scalable Architectures and Systems and professor of computer science, was recognized for his research in next-generation architectures. Önder is principal investigator of three National Science Foundation (NSF) grants, and he has three NSF grant proposals under review.

“Soner is one of our very top researchers in terms of research expenditures and new awards,” said Tim Havens, ICC director and the William and Gloria Jackson Associate Professor of Computer Systems. “He is also active in developing and implementing the ICC vision and activities.”

Kevin Trewartha, a member of the ICC’s Center for Human-Centered Computing, was recognized for his interdisciplinary and collaborative research at the intersection of technology and human motor movement. Trewartha is an assistant professor with a dual appointment in the departments of Cognitive and Learning Sciences and Kinesiology and Integrative Physiology.

“Kevin encompasses the best of the ICC vision,” said Beth Veinott, director of the ICC Center for Human-Centered Computing and associate professor of cognitive and learning sciences.

Trewartha is co-principal investigator, with ICC member Shane Mueller, of a new, three-year, interdisciplinary and collaborative project funded by the National Institutes of Health. For this research, Trewartha and Mueller are working with UP Health Systems Portage and five graduate and three undergraduate students to investigate how technology supports earlier diagnosis of the neurodegenerative diseases.

Bo Chen, a member of the ICC’s Center for Cyber-Physical Systems and assistant professor of computer science, was recognized for his teaching and research in cybersecurity of mobile devices.

Chen is the co-PI of two external grants on cybersecurity from the National Science Administration, and he has submitted numerous cybersecurity proposals to NSF, NSA, Microsoft, and Google.

“Dr. Bo Chen has demonstrated achievements and contributions to the mission of the ICC since coming to Michigan Tech as a tenure-track CS faculty in fall ’17,” said ICC members Guy Hembroff and Yu Cai in their nomination, adding that during that short time, “Dr. Chen has published one book, five journal papers, and 10 conference papers, and in 2017 he was awarded a Distinguished Paper Award from the prestigious cybersecurity venue, the Annual Computer Security Application Conference (ACSAC ’17).”

Chen is the faculty coach for the MTU NCL (National Cyber League) cyber competition team, and during the fall 2018 regular season under Chen’s leadership, a Michigan Tech CS undergraduate student placed 36th out of 3,350 players in NCL cyber competition. Dr. Chen was also recently recognized for receiving an exceptional “average of seven dimensions” student evaluation score for his teaching, among additional accolades.

The ICC, founded in 2015, promotes collaborative, cross-disciplinary research and learning experiences in the areas of cyber-physical systems, cybersecurity, data sciences, human-centered computing, and scalable architectures and systems. It provides faculty and students the opportunity to work across organizational boundaries to create an environment that mirrors contemporary technological innovation.

Five research centers comprise the ICC. The ICC’s 50 members, who represent 15 academic units at Michigan Tech, are collaborating to conduct impactful research, make valuable contributions in the field of computing, and solve problems of critical national importance.

Visit the ICC website at icc.mtu.edu. Contact the ICC at icc-contact@mtu.edu or 906-487-2518.

Continue Reading →

2017 ICC Achievement Awards Presented at ICC Annual Retreat

Published

ICC Annual Retreat was held on April 21. Co-Director Dan Fuhrmann presented ICC Achievement Awards to two researchers for their outstanding research and honorable contributions to the ICC in 2017. Zhuo Feng from the Center for Scalable Architectures and Systems (SAS) and Shane Mueller from the Center for Human-Centered Computing (HCC) were this year’s recipients.

Shane Mueller is Associate Professor in the Department of Cognitive and Learning Sciences with an expertise in Cognitive and Computational Modeling. He has recently been awardedDARPA’s Explainable AI (XAI) Grant to develop naturalistic theories of explanation with AI systems and to develop a computational cognitive model of explanatory reasoning.  In addition to this effort, he has served as Co-PI of  several proposals in collaboration with other HCC members from the KIP, CS, and Math departments. He has continuously published his works in top journals and conferences, such as IEEE and Cognitive Modeling Communities and organized several conferences. Another significant achievement is developing PEBL: The Free Psychology Experiment Building Language for HCI and Psychology Researchers, which is widely used across the world. Zhuo Feng is Associate Professor in the Department of Electrical and Computer Engineering. Zhuo has received funding as the sole PI on three National Science Foundation (NSF) grants since 2014 with a total of $1.1 million. He received a Faculty Early Career Development (CAREER) Award from NSF in 2014, a Best Paper Award from ACM/IEEE Design Automation Conference (DAC) in 2013, and two Best Paper AwardNominations from IEEE/ACM International Conference on Computer-Aided Design (ICCAD) in 2006 and 2008. His publications include 16 journal papers (14 IEEE/ACM Transactions) and 34 ACM/IEEE conference papers.

Continue Reading →