OpenRaiser/Intern-Atlas huggingface dataset:
Particle Merging-and-Splitting
Venue: arXiv cs.GR 2021
Year: 2021

Robustly handling collisions between individual particles in a large particle-based simulation has been a challenging problem. We introduce particle merging-and-splitting, a simple scheme for robustly handling collisions between particles that prevents inter-penetrations of separate objects without introducing numerical instabilities. This scheme merges colliding particles at the beginning of the time-step and then splits them at the end of the time-step. Thus, collisions last for the duration of a time-step, allowing neighboring particles of the colliding particles to influence each other. We show that our merging-and-splitting method is effective in robustly handling collisions and avoiding penetrations in particle-based simulations. We also show how our merging-and-splitting approach can be used for coupling different simulation systems using different and otherwise incompatible integrators. We present simulation tests involving complex solid-fluid interactions, including solid fractures generated by fluid interactions.
Loop Transformations using Clang's Abstract Syntax Tree
Venue: arXiv cs.PL 2021
Year: 2021

OpenMP 5.1 introduced the first loop nest transformation directives unroll and tile, and more are expected to be included in OpenMP 6.0. We discuss the two Abstract Syntax Tree (AST) representations used by Clang's implementation that is currently under development. The first representation is designed for compatibility with the existing implementation and stores the transformed loop nest in a shadow AST next to the syntactical AST. The second representation introduces a new meta AST-node OMPCanonicalLoop that guarantees that the semantic requirements of an OpenMP loop are met, and a CanonicalLoopInfo type that the OpenMPIRBuilder uses to represent literal and transformed loops. This second approach provides a better abstraction of loop semantics, removes the need for shadow AST nodes that are only relevant for code generation, allows sharing the implementation with other front-ends such as flang, but depends on the OpenMPIRBuilder which is currently under development.
An Automated Approach to Reasoning About Task-Oriented Insights in Responsive Visualization
Venue: arXiv cs.HC 2021
Year: 2021

Authors often transform a large screen visualization for smaller displays through rescaling, aggregation and other techniques when creating visualizations for both desktop and mobile devices (i.e., responsive visualization). However, transformations can alter relationships or patterns implied by the large screen view, requiring authors to reason carefully about what information to preserve while adjusting their design for the smaller display. We propose an automated approach to approximating the loss of support for task-oriented visualization insights (identification, comparison, and trend) in responsive transformation of a source visualization. We operationalize identification, comparison, and trend loss as objective functions calculated by comparing properties of the rendered source visualization to each realized target (small screen) visualization. To evaluate the utility of our approach, we train machine learning models on human ranked small screen alternative visualizations across a set of source visualizations. We find that our approach achieves an accuracy of 84% (random forest model) in ranking visualizations. We demonstrate this approach in a prototype responsive visualization recommender that enumerates responsive transformations using Answer Set Programming and evaluates the preservation of task-oriented insights using our loss measures. We discuss implications of our approach for the development of automated and semi-automated responsive visualization recommendation.
Automatic Fairness Testing of Neural Classifiers through Adversarial Sampling
Venue: arXiv cs.LG 2021
Year: 2021

Although deep learning has demonstrated astonishing performance in many applications, there are still concerns about its dependability. One desirable property of deep learning applications with societal impact is fairness (i.e., non-discrimination). Unfortunately, discrimination might be intrinsically embedded into the models due to the discrimination in the training data. As a countermeasure, fairness testing systemically identifies discriminatory samples, which can be used to retrain the model and improve the model's fairness. Existing fairness testing approaches however have two major limitations. Firstly, they only work well on traditional machine learning models and have poor performance (e.g., effectiveness and efficiency) on deep learning models. Secondly, they only work on simple structured (e.g., tabular) data and are not applicable for domains such as text. In this work, we bridge the gap by proposing a scalable and effective approach for systematically searching for discriminatory samples while extending existing fairness testing approaches to address a more challenging domain, i.e., text classification. Compared with state-of-the-art methods, our approach only employs lightweight procedures like gradient computation and clustering, which is significantly more scalable and effective. Experimental results show that on average, our approach explores the search space much more effectively (9.62 and 2.38 times more than the state-of-the-art methods respectively on tabular and text datasets) and generates much more discriminatory samples (24.95 and 2.68 times) within a same reasonable time. Moreover, the retrained models reduce discrimination by 57.2% and 60.2% respectively on average.
Ultra Low Power 3D-Embedded Convolutional Neural Network Cube Based on $α$-IGZO Nanosheet and Bi-Layer Resistive Memory
Venue: arXiv cs.ET 2021
Year: 2021

In this paper we propose and evaluate the performance of a 3D-embedded neuromorphic computation block based on indium gallium zinc oxide ($α$-IGZO) based nanosheet transistor and bi-layer resistive memory devices. We have fabricated bi-layer resistive random-access memory (RRAM) devices with Ta$_2$O$_5$ and Al$_2$O$_3$ layers. The device has been characterized and modeled. The compact models of RRAM and $α$-IGZO based embedded nanosheet structures have been used to evaluate the system-level performance of 8 vertically stacked $α$-IGZO based nanosheet layers with RRAM for neuromorphic applications. The model considers the design space with uniform bit line (BL), select line (SL), and word line (WL) resistance. Finally, we have simulated the weighted sum operation with our proposed 8-layer stacked nanosheet-based embedded memory and evaluated the performance for VGG-16 convolutional neural network (CNN) for Fashion-MNIST and CIFAR-10 data recognition, which yielded 92% and 75% accuracy respectively with drop out layers amid device variation.
Towards autonomic orchestration of machine learning pipelines in future networks
Venue: arXiv cs.NI 2021
Year: 2021

Machine learning (ML) techniques are being increasingly used in mobile networks for network planning, operation, management, optimisation and much more. These techniques are realised using a set of logical nodes known as ML pipeline. A single network operator might have thousands of such ML pipelines distributed across its network. These pipelines need to be managed and orchestrated across network domains. Thus it is essential to have autonomic multi-domain orchestration of ML pipelines in mobile networks. International Telecommunications Union (ITU) has provided an architectural framework for management and orchestration of ML pipelines in future networks. We extend this framework to enable autonomic orchestration of ML pipelines across multiple network domains. We present our system architecture and describe its application using a smart factory use case. Our work allows autonomic orchestration of multi-domain ML pipelines in a standardised, technology agnostic, privacy preserving fashion.
Dynamic Transformer for Efficient Machine Translation on Embedded Devices
Venue: arXiv cs.CL 2021
Year: 2021

The Transformer architecture is widely used for machine translation tasks. However, its resource-intensive nature makes it challenging to implement on constrained embedded devices, particularly where available hardware resources can vary at run-time. We propose a dynamic machine translation model that scales the Transformer architecture based on the available resources at any particular time. The proposed approach, 'Dynamic-HAT', uses a HAT SuperTransformer as the backbone to search for SubTransformers with different accuracy-latency trade-offs at design time. The optimal SubTransformers are sampled from the SuperTransformer at run-time, depending on latency constraints. The Dynamic-HAT is tested on the Jetson Nano and the approach uses inherited SubTransformers sampled directly from the SuperTransformer with a switching time of <1s. Using inherited SubTransformers results in a BLEU score loss of <1.5% because the SubTransformer configuration is not retrained from scratch after sampling. However, to recover this loss in performance, the dimensions of the design space can be reduced to tailor it to a family of target hardware. The new reduced design space results in a BLEU score increase of approximately 1% for sub-optimal models from the original design space, with a wide range for performance scaling between 0.356s - 1.526s for the GPU and 2.9s - 7.31s for the CPU.
A proof theoretic basis for relational semantics
Venue: arXiv cs.LO 2021
Year: 2021

Logic has proved essential for formally modeling software based systems. Such formal descriptions, frequently called specifications, have served not only as requirements documentation and formalisation, but also for providing the mathematical foundations for their analysis and the development of automated reasoning tools. Logic is usually studied in terms of its two inherent aspects: syntax and semantics. The relevance of the latter resides in the fact that producing logical descriptions of real-world phenomena, requires people to agree on how such descriptions are to be interpreted and understood by human beings, so that systems can be built with confidence in accordance with their specification. On the more practical side, the metalogical relation between syntax and semantics, determines important aspects of the conclusions one can draw from the application of certain analysis techniques, like model checking. Abstract model theory (i.e., the mathematical perspective on semantics of logical languages) is of little practical value to software engineering endeavours. From our point of view, values (those that can be assigned to constants and variables) should not be just points in a platonic domain of interpretation, but elements that can be named by means of terms over the signature of the specification. In a nutshell, we are not interested in properties that require any semantic information not representable using the available syntax. In this paper we present a framework supporting the proof theoretical formalisation of classes of relational models for behavioural logical languages, whose domains of discourse are guaranteed to be formed exclusively by nameable values.
Predictable Bandwidth Slicing with Open vSwitch
Venue: arXiv cs.NI 2021
Year: 2021

Software switching, a.k.a virtual switching, plays a vital role in network virtualization and network function virtualization, enhances configurability, and reduces deployment and operational costs. Software switching also facilitates the development of edge and fog computing networks by allowing the use of commodity hardware for both data processing and packet switching. Despite these benefits, characterizing and ensuring deterministic performance with software switches is harder, compared to physical switching appliances. In particular, achieving deterministic performance is essential to adopt software switching in mission-critical applications, especially those deployed in edge and fog computing architectures. In this paper, we study the impact of switch configurations on bandwidth slicing and predictable packet latency. We demonstrate that latency and predictability are dependent on the implementation of the bandwidth slicing mechanism and that the packet schedulers used in OVS Kernel-Path and OVS-DPDK each focus on different aspects of switching performance.
DeHumor: Visual Analytics for Decomposing Humor
Venue: arXiv cs.CL 2021
Year: 2021

Despite being a critical communication skill, grasping humor is challenging -- a successful use of humor requires a mixture of both engaging content build-up and an appropriate vocal delivery (e.g., pause). Prior studies on computational humor emphasize the textual and audio features immediately next to the punchline, yet overlooking longer-term context setup. Moreover, the theories are usually too abstract for understanding each concrete humor snippet. To fill in the gap, we develop DeHumor, a visual analytical system for analyzing humorous behaviors in public speaking. To intuitively reveal the building blocks of each concrete example, DeHumor decomposes each humorous video into multimodal features and provides inline annotations of them on the video script. In particular, to better capture the build-ups, we introduce content repetition as a complement to features introduced in theories of computational humor and visualize them in a context linking graph. To help users locate the punchlines that have the desired features to learn, we summarize the content (with keywords) and humor feature statistics on an augmented time matrix. With case studies on stand-up comedy shows and TED talks, we show that DeHumor is able to highlight various building blocks of humor examples. In addition, expert interviews with communication coaches and humor researchers demonstrate the effectiveness of DeHumor for multimodal humor analysis of speech content and vocal delivery.
As Easy as 1, 2, 3: Behavioural Testing of NMT Systems for Numerical Translation
Venue: arXiv cs.CL 2021
Year: 2021

Mistranslated numbers have the potential to cause serious effects, such as financial loss or medical misinformation. In this work we develop comprehensive assessments of the robustness of neural machine translation systems to numerical text via behavioural testing. We explore a variety of numerical translation capabilities a system is expected to exhibit and design effective test examples to expose system underperformance. We find that numerical mistranslation is a general issue: major commercial systems and state-of-the-art research models fail on many of our test examples, for high- and low-resource languages. Our tests reveal novel errors that have not previously been reported in NMT systems, to the best of our knowledge. Lastly, we discuss strategies to mitigate numerical mistranslation.
SpecBox: A Label-Based Transparent Speculation Scheme Against Transient Execution Attacks
Venue: arXiv cs.CR 2021
Year: 2021

Speculative execution techniques have been a cornerstone of modern processors to improve instruction-level parallelism. However, recent studies showed that this kind of techniques could be exploited by attackers to leak secret data via transient execution attacks, such as Spectre. Many defenses are proposed to address this problem, but they all face various challenges: (1) Tracking data flow in the instruction pipeline could comprehensively address this problem, but it could cause pipeline stalls and incur high performance overhead; (2) Making side effect of speculative execution imperceptible to attackers, but it often needs additional storage components and complicated data movement operations. In this paper, we propose a label-based transparent speculation scheme called SpecBox. It dynamically partitions the cache system to isolate speculative data and non-speculative data, which can prevent transient execution from being observed by subsequent execution. Moreover, it uses thread ownership semaphores to prevent speculative data from being accessed across cores. In addition, SpecBox also enhances the auxiliary components in the cache system against transient execution attacks, such as hardware prefetcher. Our security analysis shows that SpecBox is secure and the performance evaluation shows that the performance overhead on SPEC CPU 2006 and PARSEC-3.0 benchmarks is small.
A Positive/Unlabeled Approach for the Segmentation of Medical Sequences using Point-Wise Supervision
Venue: arXiv cs.CV 2021
Year: 2021

The ability to quickly annotate medical imaging data plays a critical role in training deep learning frameworks for segmentation. Doing so for image volumes or video sequences is even more pressing as annotating these is particularly burdensome. To alleviate this problem, this work proposes a new method to efficiently segment medical imaging volumes or videos using point-wise annotations only. This allows annotations to be collected extremely quickly and remains applicable to numerous segmentation tasks. Our approach trains a deep learning model using an appropriate Positive/Unlabeled objective function using sparse point-wise annotations. While most methods of this kind assume that the proportion of positive samples in the data is known a-priori, we introduce a novel self-supervised method to estimate this prior efficiently by combining a Bayesian estimation framework and new stopping criteria. Our method iteratively estimates appropriate class priors and yields high segmentation quality for a variety of object types and imaging modalities. In addition, by leveraging a spatio-temporal tracking framework, we regularize our predictions by leveraging the complete data volume. We show experimentally that our approach outperforms state-of-the-art methods tailored to the same problem.
A Miniature Biological Eagle-Eye Vision System for Small Target Detection
Venue: arXiv cs.CV 2021
Year: 2021

Small target detection is known to be a challenging problem. Inspired by the structural characteristics and physiological mechanism of eagle-eye, a miniature vision system is designed for small target detection in this paper. First, a hardware platform is established, which consists of a pan-tilt, a short-focus camera and a long-focus camera. Then, based on the visual attention mechanism of eagle-eye, the cameras with different focal lengths are controlled cooperatively to achieve small target detection. Experimental results show that the designed biological eagle-eye vision system can accurately detect small targets, which has a strong adaptive ability.
A Theory of PAC Learnability of Partial Concept Classes
Venue: arXiv cs.LG 2021
Year: 2021

We extend the theory of PAC learning in a way which allows to model a rich variety of learning tasks where the data satisfy special properties that ease the learning process. For example, tasks where the distance of the data from the decision boundary is bounded away from zero. The basic and simple idea is to consider partial concepts: these are functions that can be undefined on certain parts of the space. When learning a partial concept, we assume that the source distribution is supported only on points where the partial concept is defined. This way, one can naturally express assumptions on the data such as lying on a lower dimensional surface or margin conditions. In contrast, it is not at all clear that such assumptions can be expressed by the traditional PAC theory. In fact we exhibit easy-to-learn partial concept classes which provably cannot be captured by the traditional PAC theory. This also resolves a question posed by Attias, Kontorovich, and Mansour 2019. We characterize PAC learnability of partial concept classes and reveal an algorithmic landscape which is fundamentally different than the classical one. For example, in the classical PAC model, learning boils down to Empirical Risk Minimization (ERM). In stark contrast, we show that the ERM principle fails in explaining learnability of partial concept classes. In fact, we demonstrate classes that are incredibly easy to learn, but such that any algorithm that learns them must use an hypothesis space with unbounded VC dimension. We also find that the sample compression conjecture fails in this setting. Thus, this theory features problems that cannot be represented nor solved in the traditional way. We view this as evidence that it might provide insights on the nature of learnability in realistic scenarios which the classical theory fails to explain.
GoTube: Scalable Stochastic Verification of Continuous-Depth Models
Venue: arXiv cs.LG 2021
Year: 2021

We introduce a new stochastic verification algorithm that formally quantifies the behavioral robustness of any time-continuous process formulated as a continuous-depth model. Our algorithm solves a set of global optimization (Go) problems over a given time horizon to construct a tight enclosure (Tube) of the set of all process executions starting from a ball of initial states. We call our algorithm GoTube. Through its construction, GoTube ensures that the bounding tube is conservative up to a desired probability and up to a desired tightness. GoTube is implemented in JAX and optimized to scale to complex continuous-depth neural network models. Compared to advanced reachability analysis tools for time-continuous neural networks, GoTube does not accumulate overapproximation errors between time steps and avoids the infamous wrapping effect inherent in symbolic techniques. We show that GoTube substantially outperforms state-of-the-art verification tools in terms of the size of the initial ball, speed, time-horizon, task completion, and scalability on a large set of experiments. GoTube is stable and sets the state-of-the-art in terms of its ability to scale to time horizons well beyond what has been previously possible.
Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields
Venue: arXiv cs.DS 2021
Year: 2021

For smooth finite fields $F_q$ (i.e., when $q-1$ factors into small primes) the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. However, the same operations over fields with no smooth order root of unity suffer from an asymptotic slowdown. The classical algorithm of Schonhage and Strassen incurred a multiplicative slowdown factor of $\log \log n$ on top of the smooth case. Recent remarkable results of Harvey, van der Hoeven and Lecerf dramatically reduced this multiplicative overhead to $\exp(\log^* (n))$. We introduce a new approach to fast algorithms for polynomial operations over all large finite fields. The key idea is to replace the group of roots of unity with a set of points $L \subset F$ suitably related to a well-chosen elliptic curve group (the set $L$ itself is not a group). The key advantage of this approach is that elliptic curve groups can be of any size in the Hasse-Weil interval $[q+1 \pm 2\sqrt{q}]$ and thus can have subgroups of large, smooth order, which an FFT-like divide and conquer algorithm can exploit. Compare this with multiplicative subgroups over whose order must divide $q-1$. For polynomials represented by their evaluation over subsets of $L$, we show that multiplication, division, degree-computation, interpolation, evaluation and Reed-Solomon encoding (also known as low-degree extension) with fixed evaluation points can all be computed with arithmetic circuits of size similar to what is achievable with the classical FFTs when the field size is special. For several problems, this yields the asymptotically smallest known arithmetic circuits even in the standard monomial representation of polynomials.