OpenRaiser/Intern-Atlas huggingface dataset:
LB4OMP: A Dynamic Load Balancing Library for Multithreaded Applications
Venue: arXiv cs.DC 2021
Year: 2021

Exascale computing systems will exhibit high degrees of hierarchical parallelism, with thousands of computing nodes and hundreds of cores per node. Efficiently exploiting hierarchical parallelism is challenging due to load imbalance that arises at multiple levels. OpenMP is the most widely-used standard for expressing and exploiting the ever-increasing node-level parallelism. The scheduling options in OpenMP are insufficient to address the load imbalance that arises during the execution of multithreaded applications. The limited scheduling options in OpenMP hinder research on novel scheduling techniques which require comparison with others from the literature. This work introduces LB4OMP, an open-source dynamic load balancing library that implements successful scheduling algorithms from the literature. LB4OMP is a research infrastructure designed to spur and support present and future scheduling research, for the benefit of multithreaded applications performance. Through an extensive performance analysis campaign, we assess the effectiveness and demystify the performance of all loop scheduling techniques in the library. We show that, for numerous applications-systems pairs, the scheduling techniques in LB4OMP outperform the scheduling options in OpenMP. Node-level load balancing using LB4OMP leads to reduced cross-node load imbalance and to improved MPI+OpenMP applications performance, which is critical for Exascale computing.
Prior-Aware Distribution Estimation for Differential Privacy
Venue: arXiv cs.DS 2021
Year: 2021

Joint distribution estimation of a dataset under differential privacy is a fundamental problem for many privacy-focused applications, such as query answering, machine learning tasks and synthetic data generation. In this work, we examine the joint distribution estimation problem given two data points: 1) differentially private answers of a workload computed over private data and 2) a prior empirical distribution from a public dataset. Our goal is to find a new distribution such that estimating the workload using this distribution is as accurate as the differentially private answer, and the relative entropy, or KL divergence, of this distribution is minimized with respect to the prior distribution. We propose an approach based on iterative optimization for solving this problem. An application of our solution won second place in the NIST 2020 Differential Privacy Temporal Map Challenge, Sprint 2.
Relative Clustering Coefficient
Venue: arXiv cs.CG 2021
Year: 2021

In this paper, we relatively extend the definition of global clustering coefficient to another clustering, which we call it relative clustering coefficient. The idea of this definition is to ignore the edges in the network that the probability of having an edge is 0. Here, we also consider a model as an example that using relative clustering coefficient is better than global clustering coefficient for comparing networks and also checking the properties of the networks.
An Improved Bound for the Tree Conjecture in Network Creation Games
Venue: arXiv cs.GT 2021
Year: 2021

We study Nash equilibria in the network creation game of Fabrikant et al.[10]. In this game a vertex can buy an edge to another vertex for a cost of $α$, and the objective of each vertex is to minimize the sum of the costs of the edges it purchases plus the sum of the distances to every other vertex in the resultant network. A long-standing conjecture states that if $α\ge n$ then every Nash equilibrium in the game is a spanning tree. We prove the conjecture holds for any $α>3n-3$.
Workflows Community Summit: Advancing the State-of-the-art of Scientific Workflows Management Systems Research and Development
Venue: arXiv cs.DC 2021
Year: 2021

Scientific workflows are a cornerstone of modern scientific computing, and they have underpinned some of the most significant discoveries of the last decade. Many of these workflows have high computational, storage, and/or communication demands, and thus must execute on a wide range of large-scale platforms, from large clouds to upcoming exascale HPC platforms. Workflows will play a crucial role in the data-oriented and post-Moore's computing landscape as they democratize the application of cutting-edge research techniques, computationally intensive methods, and use of new computing platforms. As workflows continue to be adopted by scientific projects and user communities, they are becoming more complex. Workflows are increasingly composed of tasks that perform computations such as short machine learning inference, multi-node simulations, long-running machine learning model training, amongst others, and thus increasingly rely on heterogeneous architectures that include CPUs but also GPUs and accelerators. The workflow management system (WMS) technology landscape is currently segmented and presents significant barriers to entry due to the hundreds of seemingly comparable, yet incompatible, systems that exist. Another fundamental problem is that there are conflicting theoretical bases and abstractions for a WMS. Systems that use the same underlying abstractions can likely be translated between, which is not the case for systems that use different abstractions. More information: https://workflowsri.org/summits/technical
Decentralised Approach for Multi Agent Path Finding
Venue: arXiv cs.MA 2021
Year: 2021

Multi Agent Path Finding (MAPF) requires identification of conflict free paths for agents which could be point-sized or with dimensions. In this paper, we propose an approach for MAPF for spatially-extended agents. These find application in real world problems like Convoy Movement Problem, Train Scheduling etc. Our proposed approach, Decentralised Multi Agent Path Finding (DeMAPF), handles MAPF as a sequence of pathplanning and allocation problems which are solved by two sets of agents Travellers and Routers respectively, over multiple iterations. The approach being decentralised allows an agent to solve the problem pertinent to itself, without being aware of other agents in the same set. This allows the agents to be executed on independent machines, thereby leading to scalability to handle large sized problems. We prove, by comparison with other distributed approaches, that the approach leads to a faster convergence to a conflict-free solution, which may be suboptimal, with lesser memory requirement.
Coopetition methodology for resource sharing in distributed OFDM-based cognitive radio networks
Venue: arXiv cs.NI 2021
Year: 2021

In this paper, we present a distributed resource allocation mechanism in cognitive radio networks, based on a new coopeti-tion methodology, which combines advantages of nodes competition and cooperation. We postulate that this new method allows for fully distributed resource management between cognitive radio devices. The presented framework is generic, however, we consider it for the application in OFDMA networks. Coopetition takes the best from cooperative and competitive problem formulation and provides the opportunity to control the balance between fairness and spectral efficiency (SE) of resource allocation. Simulation results confirm that coopetition allows for efficient resource utilization, and may be used practically in wireless cognitive networks.
StreamBrain: An HPC Framework for Brain-like Neural Networks on CPUs, GPUs and FPGAs
Venue: arXiv cs.DC 2021
Year: 2021

The modern deep learning method based on backpropagation has surged in popularity and has been used in multiple domains and application areas. At the same time, there are other -- less-known -- machine learning algorithms with a mature and solid theoretical foundation whose performance remains unexplored. One such example is the brain-like Bayesian Confidence Propagation Neural Network (BCPNN). In this paper, we introduce StreamBrain -- a framework that allows neural networks based on BCPNN to be practically deployed in High-Performance Computing systems. StreamBrain is a domain-specific language (DSL), similar in concept to existing machine learning (ML) frameworks, and supports backends for CPUs, GPUs, and even FPGAs. We empirically demonstrate that StreamBrain can train the well-known ML benchmark dataset MNIST within seconds, and we are the first to demonstrate BCPNN on STL-10 size networks. We also show how StreamBrain can be used to train with custom floating-point formats and illustrate the impact of using different bfloat variations on BCPNN using FPGAs.
Aerial Reconfigurable Intelligent Surface-Aided Wireless Communication Systems
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we propose and investigate an aerial reconfigurable intelligent surface (aerial-RIS)-aided wireless communication system. Specifically, considering practical composite fading channels, we characterize the air-to-ground (A2G) links by Namkagami-m small-scale fading and inverse-Gamma large-scale shadowing. To investigate the delay-limited performance of the proposed system, we derive a tight approximate closed-form expression for the end-to-end outage probability (OP). Next, considering a mobile environment, where performance analysis is intractable, we rely on machine learning-based performance prediction to evaluate the performance of the mobile aerial-RIS-aided system. Specifically, taking into account the three-dimensional (3D) spatial movement of the aerial-RIS, we build a deep neural network (DNN) to accurately predict the OP. We show that: (i) fading and shadowing conditions have strong impact on the OP, (ii) as the number of reflecting elements increases, aerial-RIS achieves higher energy efficiency (EE), and (iii) the aerial-RIS-aided system outperforms conventional relaying systems.
Long-time integration of parametric evolution equations with physics-informed DeepONets
Venue: arXiv cs.LG 2021
Year: 2021

Ordinary and partial differential equations (ODEs/PDEs) play a paramount role in analyzing and simulating complex dynamic processes across all corners of science and engineering. In recent years machine learning tools are aspiring to introduce new effective ways of simulating PDEs, however existing approaches are not able to reliably return stable and accurate predictions across long temporal horizons. We aim to address this challenge by introducing an effective framework for learning infinite-dimensional operators that map random initial conditions to associated PDE solutions within a short time interval. Such latent operators can be parametrized by deep neural networks that are trained in an entirely self-supervised manner without requiring any paired input-output observations. Global long-time predictions across a range of initial conditions can be then obtained by iteratively evaluating the trained model using each prediction as the initial condition for the next evaluation step. This introduces a new approach to temporal domain decomposition that is shown to be effective in performing accurate long-time simulations for a wide range of parametric ODE and PDE systems, from wave propagation, to reaction-diffusion dynamics and stiff chemical kinetics, all at a fraction of the computational cost needed by classical numerical solvers.
Impact of Blockchain Technology on Electric Power Grids -- A case study in LO3 Energy
Venue: arXiv cs.CR 2021
Year: 2021

The increasing amount of distributed energy resources including renewable energy systems and electric vehicles is expected to change electric power grids significantly, where conventional consumers are transformed to prosumers since they can produce electricity as well. In such an ecosystem, prosumers can start offering their excess energy to supply demands of the other customers on the grids behind the meter without interference of distribution system operators (DSO). Besides, DSOs require more accurate and more frequent data form prosumers' net demand to be able to operate their network efficiently. The main challenge in these new distribution grids is the amount of data that needs to be collected in this platform is unbelievably high, and more immortally, prosumers will likely refuse to share their information with DSOs due to their potential privacy and economic concerns. Blockchain technology as an efficient distributed solution for management of data and financial transactions, has been considered to solve this trust issue. With blockchain-based solutions, data and financial transactions between all parties will take placed through distributed ledgers without any interference from an intermediary. In this paper, impacts of blockchain technologies on electric power industry is studied. The paper specifically focuses on LO3 Energy -- one of startups applying blockchain to electric power grids -- their blockchain-based solution called Exergy, and their use cases to implement such solutions.
Separating Boundary Points via Structural Regularization for Very Compact Clusters
Venue: arXiv cs.CV 2021
Year: 2021

Clustering algorithms have significantly improved along with Deep Neural Networks which provide effective representation of data. Existing methods are built upon deep autoencoder and self-training process that leverages the distribution of cluster assignments of samples. However, as the fundamental objective of the autoencoder is focused on efficient data reconstruction, the learnt space may be sub-optimal for clustering. Moreover, it requires highly effective codes (i.e., representation) of data, otherwise the initial cluster centers often cause stability issues during self-training. Many state-of-the-art clustering algorithms use convolution operation to extract efficient codes but their applications are limited to image data. In this regard, we propose an end-to-end deep clustering algorithm, i.e., Very Compact Clusters (VCC). VCC takes advantage of distributions of local relationships of samples near the boundary of clusters, so that they can be properly separated and pulled to cluster centers to form compact clusters. Experimental results on various datasets illustrate that our proposed approach achieves competitive clustering performance against most of the state-of-the-art clustering methods for both image and non-image data, and its results can be easily qualitatively seen in the learnt low-dimensional space.
Input Augmentation Improves Constrained Beam Search for Neural Machine Translation: NTT at WAT 2021
Venue: arXiv cs.CL 2021
Year: 2021

This paper describes our systems that were submitted to the restricted translation task at WAT 2021. In this task, the systems are required to output translated sentences that contain all given word constraints. Our system combined input augmentation and constrained beam search algorithms. Through experiments, we found that this combination significantly improves translation accuracy and can save inference time while containing all the constraints in the output. For both En->Ja and Ja->En, our systems obtained the best evaluation performances in automatic evaluation.
Mode recovery in neural autoregressive sequence modeling
Venue: arXiv cs.LG 2021
Year: 2021

Despite its wide use, recent studies have revealed unexpected and undesirable properties of neural autoregressive sequence models trained with maximum likelihood, such as an unreasonably high affinity to short sequences after training and to infinitely long sequences at decoding time. We propose to study these phenomena by investigating how the modes, or local maxima, of a distribution are maintained throughout the full learning chain of the ground-truth, empirical, learned and decoding-induced distributions, via the newly proposed mode recovery cost. We design a tractable testbed where we build three types of ground-truth distributions: (1) an LSTM based structured distribution, (2) an unstructured distribution where probability of a sequence does not depend on its content, and (3) a product of these two which we call a semi-structured distribution. Our study reveals both expected and unexpected findings. First, starting with data collection, mode recovery cost strongly relies on the ground-truth distribution and is most costly with the semi-structured distribution. Second, after learning, mode recovery cost from the ground-truth distribution may increase or decrease compared to data collection, with the largest cost degradation occurring with the semi-structured ground-truth distribution. Finally, the ability of the decoding-induced distribution to recover modes from the learned distribution is highly impacted by the choices made earlier in the learning chain. We conclude that future research must consider the entire learning chain in order to fully understand the potentials and perils and to further improve neural autoregressive sequence models.
Jointly Optimize Coding and Node Selection for Distributed Computing over Wireless Edge Networks
Venue: arXiv cs.DC 2021
Year: 2021

This work aims to jointly optimize the coding and node selection to minimize the processing time for distributed computing tasks over wireless edge networks. Since the joint optimization problem formulation is NP-hard and nonlinear, we leverage the discrete characteristic of its decision variables to transform the problem into an equivalent linear formulation. This linearization can guarantee to find the optimal solutions and significantly reduce the problem's complexity. Simulations based on real-world datasets show that the proposed approach can reduce the total processing time up to 2.3 times compared with that of state-of-the-art approach.
Hyperspace Neighbor Penetration Approach to Dynamic Programming for Model-Based Reinforcement Learning Problems with Slowly Changing Variables in A Continuous State Space
Venue: arXiv cs.LG 2021
Year: 2021

Slowly changing variables in a continuous state space constitute an important category of reinforcement learning and see its application in many domains, such as modeling a climate control system where temperature, humidity, etc. change slowly over time. However, this subject is less addressed in recent studies. Classical methods with certain variants, such as Dynamic Programming with Tile Coding which discretizes the state space, fail to handle slowly changing variables because those methods cannot capture the tiny changes in each transition step, as it is computationally expensive or impossible to establish an extremely granular grid system. In this paper, we introduce a Hyperspace Neighbor Penetration (HNP) approach that solves the problem. HNP captures in each transition step the state's partial "penetration" into its neighboring hyper-tiles in the gridded hyperspace, thus does not require the transition to be inter-tile in order for the change to be captured. Therefore, HNP allows for a very coarse grid system, which makes the computation feasible. HNP assumes near linearity of the transition function in a local space, which is commonly satisfied. In summary, HNP can be orders of magnitude more efficient than classical method in handling slowly changing variables in reinforcement learning. We have made an industrial implementation of NHP with a great success.
Deterministic Mincut in Almost-Linear Time
Venue: arXiv cs.DS 2021
Year: 2021

We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in $m^{1+o(1)}$ time, answering an open question of Karger from the 1990s. To obtain our result, we de-randomize the construction of the \emph{skeleton} graph in Karger's near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, which involves harnessing the expander decomposition framework introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications.
3D Semantic Mapping from Arthroscopy using Out-of-distribution Pose and Depth and In-distribution Segmentation Training
Venue: arXiv cs.RO 2021
Year: 2021

Minimally invasive surgery (MIS) has many documented advantages, but the surgeon's limited visual contact with the scene can be problematic. Hence, systems that can help surgeons navigate, such as a method that can produce a 3D semantic map, can compensate for the limitation above. In theory, we can borrow 3D semantic mapping techniques developed for robotics, but this requires finding solutions to the following challenges in MIS: 1) semantic segmentation, 2) depth estimation, and 3) pose estimation. In this paper, we propose the first 3D semantic mapping system from knee arthroscopy that solves the three challenges above. Using out-of-distribution non-human datasets, where pose could be labeled, we jointly train depth+pose estimators using selfsupervised and supervised losses. Using an in-distribution human knee dataset, we train a fully-supervised semantic segmentation system to label arthroscopic image pixels into femur, ACL, and meniscus. Taking testing images from human knees, we combine the results from these two systems to automatically create 3D semantic maps of the human knee. The result of this work opens the pathway to the generation of intraoperative 3D semantic mapping, registration with pre-operative data, and robotic-assisted arthroscopy
FRI-TEM: Time Encoding Sampling of Finite-Rate-of-Innovation Signals
Venue: arXiv cs.IT 2021
Year: 2021

Classical sampling is based on acquiring signal amplitudes at specific points in time, with the minimal sampling rate dictated by the degrees of freedom in the signal. The samplers in this framework are controlled by a global clock that operates at a rate greater than or equal to the minimal sampling rate. At high sampling rates, clocks are power-consuming and prone to electromagnetic interference. An integrate-and-fire time encoding machine (IF-TEM) is an alternative power-efficient sampling mechanism which does not require a global clock. Here, the samples are irregularly spaced threshold-based samples. In this paper, we investigate the problem of sampling finite-rate-of-innovation (FRI) signals using an IF-TEM. We provide theoretical recovery guarantees for an FRI signal with arbitrary pulse shape and without any constraint on the minimum separation between the pulses. In particular, we show how to design a sampling kernel, IF-TEM, and recovery method such that the FRI signals are perfectly reconstructed. We then propose a modification to the sampling kernel to improve noise robustness. Our results enable designing low-cost and energy-efficient analog-to-digital converters for FRI signals.
Multiway Online Correlated Selection
Venue: arXiv cs.DS 2021
Year: 2021

We give a $0.5368$-competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was $0.5086$ due to Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020). They achieved their breakthrough result by developing a subroutine called \emph{online correlated selection} (OCS) which takes as input a sequence of pairs and selects one item from each pair. Importantly, the selections the OCS makes are negatively correlated. We achieve our result by defining \emph{multiway} OCSes which receive arbitrarily many elements at each step, rather than just two. In addition to better competitive ratios, our formulation allows for a simpler reduction from edge-weighted online bipartite matching to OCSes. While Fahrbach et al. used a factor-revealing linear program to optimize the competitive ratio, our analysis directly connects the competitive ratio to the parameters of the multiway OCS. Finally, we show that the formulation of Farhbach et al. can achieve a competitive ratio of at most $0.5239$, confirming that multiway OCSes are strictly more powerful.