Search

Running static analysis rules in the wild as part of a commercial service demands special consideration of time limits and scalability, given the large and diverse real-world workloads that the rules are evaluated on. Furthermore, these rules do not run in isolation, which exposes opportunities for reuse of partial evaluation results across rules. In our work on Amazon CodeGuru Reviewer, and its underlying rule-authoring toolkit known as the Guru Query Language (GQL), we have encountered performance and scalability challenges, and identified corresponding optimization opportunities, such as caching, indexing, and customization of data-flow specification, which rule authors can take advantage of as built-in GQL constructs. Our experimental evaluation of a dataset of open-source GitHub repositories shows 3× speedup and perfect recall using indexing-based configurations, 2× speedup and 51% increase on the number of findings for caching-based optimization. Customizing the data-flow specification, such as expanding the tracking scope, can yield a remarkable increase in the number of findings, as much as 136%. However, this enhancement comes at the expense of a longer analysis time. Our evaluations emphasize the importance of customizing the data-flow specification, particularly when users operate under time constraints. This customization helps the analysis complete within the given time frame, ultimately leading to improved recall. [ABSTRACT FROM AUTHOR]

This paper presents a Graphical User Interface (GUI) Builder for embedded systems and Cyber-Physical Systems (CPSs). The hardware platforms used in CPSs may employ physical devices without graphical and user-input capabilities, or devices that may be placed on multiple remote locations, often with difficult physical access, that brings new challenges to GUI design. The proposed tool, integrated within the IOPT-Flow framework, enables a new approach to answer these challenges. This framework supports the development of embedded systems and distributed CPSs, offering a set of web-based tools for model edition, simulation, and implementation on physical devices. Systems are designed using graphical models combining Data-flows, Signals, and Petri nets, that permit the specification of remote communication channels just by drawing arcs. The new GUI Builder tool uses this infrastructure to automate the creation of graphical user interfaces for embedded systems and distributed CPSs, benefiting from a development with combined design, validation and automatic code generation methods. Finally, an application example of a power wheelchair controller integrating a GUI, is presented.

Boson sampling (BS) is viewed to be an accessible quantum computing paradigm to demonstrate computational advantage compared to classical computers. In this context, the evolution of permanent calculation algorithms attracts a significant attention as the simulation of BS experiments involves the evaluation of vast number of permanents. For this reason, we generalize the Balasubramanian–Bax–Franklin–Glynn permanent formula, aiming to efficiently integrate it into the BS strategy of Clifford and Clifford (2020 Faster classical boson sampling). A reduction in simulation complexity originating from multiplicities in photon occupation was achieved through the incorporation of a n-ary Gray code ordering of the addends during the permanent evaluation. Implementing the devised algorithm on FPGA-based data-flow engines, we leverage the resulting tool to accelerate boson sampling simulations for up to 40 photons. Drawing samples from a 60-mode interferometer, the achieved rate averages around 80 s per sample, employing 4 FPGA chips. The developed design facilitates the simulation of both ideal and lossy boson sampling experiments.

Over the past few years, attention is shining in the field of deep learning, especially in the domain of natural language processing (NLP). Its impressive effectiveness, along with ubiquitous implementations, have aroused our interest in efficiently scheduling the data-flow of corresponding computations onto architectures with many computing units to realize parallel computing. In this paper, based on manually analyzing the optimum scheduling solutions for small instances, which are obtained by a satisfiability checking (SAT) solver, we propose a general scheduling solution to parallelize the processing of attention layers that are widely adopted in recent deep learning models. According to the solution, for the proposed hardware system with m processing elements (PEs) connected in a unidirectional ring, a m-time speed up is achievable. For two specific application schemes of attention, we respectively recognize that almost 25% and 50% of the original computations have become redundant under those certain circumstances. To avoid unnecessary computing with corresponding gains in processing latency, we have come up with strategies of optimization accordingly, which further lead to another two scheduling solutions. By avoiding the redundancy, the adoptions of the optimized scheduling solutions are able to additionally bring near 25% and 50% reduction in execution cycles, respectively for the two application schemes. To prove the correctness of these solutions, we have mathematically revealed their validity, as well as utilized SAT solver to conduct the verification by adopting the solutions themselves as additional constraints for the formulated SAT problems. [ABSTRACT FROM AUTHOR]

The data explosion and faster data analysis demand have spawned emerging applications that operate over myriads of data and exhibit large memory footprints with low data reuse rate. Such characteristics lead to enormous data movements across the memory hierarchy and pose significant pressure on modern communication fabrics and memory subsystems. To mitigate the worsening gap between high processor computation density and deficient memory bandwidth, memory networks, and near-data processing techniques are proposed to keep improving system performance and energy efficiency. In this article, we propose Active-Routing, an in-network near-data processing architecture for data-flow execution, which enables computation en-route by exploiting patterns of aggregation over intermediate results. The proposed architecture leverages the massive memory cube- and vault-level parallelism as well as network concurrency to optimize the aggregation operations along a dynamically built Active-Routing Tree. It also introduces page granular computation offloading to amortize the offloading overhead and improve the throughput. Compared to the state-of-the-art processing-in-memory architecture, the evaluations show that the baseline Active-Routing can achieve up to 7× speedup with an average of 60 percent performance improvement, and reduce the energy-delay product by 80 percent across various benchmarks. Further optimizations with vault-level parallelism and page granular offloading can achieve an extra order of magnitude improvement. [ABSTRACT FROM AUTHOR]

With the proliferation of smart embedded devices, cyber physical social computing and networking systems (CPSCN) are emerging as a next generation of social networks. Unlike traditional social networks that run on cloud-based infrastructure, CPSCN systems usually depend on a large number of distributed, heterogeneous devices, such as mobile phones, smart vehicles, or network access points. These computing resources, which are often referred to as fog computing systems, provide a gateway to the physical world, and thus offer new possibilities for social applications. Unfortunately, building CPSCN systems that leverage fog computing infrastructure is not straightforward. Significant challenges arise from the large scale distribution of computing resources over a wide area, and the dynamic nature of multiple, possibly mobile, hosts. In this paper, we extend our previous work on a distributed dataflow programming model and propose an application platform for realizing CPSCN systems. A key aspect of our work is the development of an exogenous coordination model, which exhibits a separation of concern between computation and communication activities, and helps resolve some of the challenges brought about by the dynamic and large scale nature of CPSCN systems.

Big data and the Internet of Things (IoT) are considered as the main paradigms when defining new information architecture projects. Accordingly, technologies that make up these solutions could have an important role to play in business information architecture. Solutions that have approached big data and the IoT as unique technology initiatives, struggle in finding value in such efforts and in the technology itself. A connection to the requirements (volume, velocity, and variety) is mandatory to reach the potential business goals. In this context, we propose a new architecture for Cognitive Internet of Things (CIoT) and big data. The proposed architecture benefits computing mechanisms by combining the data WareHouse (DWH) and Data Lake (DL), and defining a tool for heterogeneous data collection. [ABSTRACT FROM AUTHOR]

The Internet of things(IoT) is now considered among the most emerging technologies aiming to interconnect heterogeneous smart devices in several areas without human interaction. From sensing and identification to data processing and storing. The Building and the monitoring of smart systems like smart homes, smart campus and smart cities pass through several stages on which different tools and platforms coexist to answer this need. In this paper, we present a survey on recent works using IoT tools to build their systems. Particularly, we classify and compare them according to layers and characteristics that we have defined such as data acquisition, data processing , software used, conformity to standards. Hence , our study aims to provide a clear vision on available functionalities during the process of building IoT systems based on most used IoT tools and to help users to choose the most adapted tool depending on their needs. [ABSTRACT FROM AUTHOR]

This paper presents two case studies used to prove the validity of some data-flow mining algorithms. We proposed the data-flow mining algorithms because most part of mining algorithms focuses on the control-flow perspective. First case study uses event logs generated by an ERP system (Navision) after we set several trackers on the data elements needed in the process analyzed; while the second case study uses the event logs generated by YAWL system. We offered a general solution of data-flow model extraction from different data sources. In order to apply the data-flow mining algorithms the event logs must comply a certain format (using InputOutput extension). But to respect this format, a set of conversion tools is needed. We depicted the conversion tools used and how we got the data-flow models. Moreover, the data-flow model is compared to the control-flow model.

The paper proposes a new data-flow based approach for the identification of backbones in infinite clusters on 2-D percolation site lattices of dimension L × L . The infinite cluster is identified first, then a multi step algorithm is applied for the reduction of the infinite cluster to its backbone. Algorithm performances are evaluated theoretically and experimentally. The algorithm is local and can therefore be efficiently implemented on data-flow parallel platforms in Θ ( L ) time if applied on percolation lattices near the critical percolation probability or in Θ ( L 2 ) in the worst case. The proposed methodology could resolve the problem of stack overflow at large systems that can appear with classical graph based algorithms, and has potential for a higher execution speed-up on parallel architectures. [ABSTRACT FROM AUTHOR]

A new cellular automata-based algorithm for labeling of connected components in n-dimensional binary lattices, for $$n \ge 2$$ , is proposed. The algorithm for 3D binary images was implemented in NetLogo and MatLab programming environments. The algorithm is local and can be efficiently implemented on data-flow parallel platforms with an average asymptotic complexity of $$\mathcal{O}(L)$$ on $$L^n $$ binary lattices. However, some worst-case arrangements of the n-dimensional lattice cells could require $$\mathcal{O}(L^{n})$$ calculation steps. [ABSTRACT FROM AUTHOR]

A hybrid execution mechanism for composite service was researched. The interaction protocol between the services was established， and the characteristic model of the execution environment was presented. In addition， the rules for dynamically selecting the execution schema were proposed. The mechanism was a combination of execution schema of the centralized control-flow and data-flow as well as the execution schema of the centralized control-flow and decentralized data-flow， which could dynamically select the execution schema according to the feature of the business and the execution environment of the composite service. And then the message with large data amount could be transferred between the services without being redirected by the central node. The experimental results showed that the dynamic selection of the execution schemas could ensure the execution efficiency of the composite service. [ABSTRACT FROM AUTHOR]

We present a first evaluation of a Programming Model for real-time streaming applications on high performance embedded multi- and many-core systems. Realistic streaming applications are highly dependent on the execution context (usually of physical world), past learned strategies, and often real-time constraints. The proposed Programming Model encompasses both real- time requirements, determinism of execution and context dependency. It is an extension of the well-known Cyclo-Static Dataflow (CSDF), for its desirable properties (determinism and composability), with two new important data-flow filters: Select-duplicate, and Transaction which retain the main properties of CSDF graphs and also provide useful features to implement real-time computational embedded applications. We evaluate the relevance of our programming model thanks to several real-life case-studies and demonstrate that our approach overcomes a range of limitations that use to be associated with CSDF models. [ABSTRACT FROM AUTHOR]

Learning how to program is a difficult task. To acquire the required skills, novice programmers must solve a broad range of programming activities, always supported with timely, rich, and accurate feedback. Automated assessment tools play a major role in fulfilling these needs, being a common presence in introductory programming courses. As programming exercises are not easy to produce and those loaded into these tools must adhere to specific format requirements, teachers often opt for reusing them for several years. Therefore, most automated assessment tools, particularly Mooshak, store hundreds of submissions to the same programming exercises, as these need to be kept after automatically processed for possible subsequent manual revision. Our dataset consists of the submissions to 16 programming exercises in Mooshak proposed in multiple years within the 2003-2020 timespan to undergraduate Computer Science students at the Faculty of Sciences from the University of Porto. In particular, we extract their code property graphs and store them as CSV files. The analysis of this data can enable, for instance, the generation of more concise and personalized feedback based on similar accepted submissions in the past, the identification of different strategies to solve a problem, the understanding of a student's thinking process, among many other findings., Competing Interests: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper., (© 2023 The Author(s).)

Data-flow is a natural approach to parallelism. However, describing dependencies and control between fine-grained data-flow tasks can be complex and present unwanted overheads. TALM (TALM is an Architecture and Language for Multi-threading) introduces a user-defined coarse-grained parallel data-flow model, where programmers identify code blocks, called super-instructions, to be run in parallel and connect them in a data-flow graph. TALM has been implemented as a hybrid Von Neumann/data-flow execution system: the Trebuchet . We have observed that TALM’s usefulness largely depends on how programmers specify and connect super-instructions. Thus, we present Couillard , a full compiler that creates, based on an annotated C-program, a data-flow graph and C-code corresponding to each super-instruction. We show that our toolchain allows one to benefit from data-flow execution and explore sophisticated parallel programming techniques, with small effort. To evaluate our system we have executed a set of real applications on a large multi-core machine. Comparison with popular parallel programming methods shows competitive speedups, while providing an easier parallel programing approach. More specifically, for an application that follows the wavefront method, running with big inputs, Trebuchet achieved up to 4.7% speedup over Intel® TBB novel flow-graph approach and up to 44% over OpenMP. [ABSTRACT FROM AUTHOR]

Modern software differs significantly from traditional computer applications that mostly process reasonably small amounts of static input data-sets in batch mode. Modern software increasingly processes massive amounts of data, whereby it is also often the case that new input data is produced and/or existing data is modified on the fly. Consequently, programming models that facilitate the development of such software are emerging. What characterizes them is that data, respectively changes thereof, implicitly flow through computation modules. The software engineer declaratively defines computations as compositions of other computations without explicitly modeling how data should flow along dependency relations between data producer and data consumer modules, letting the runtime to automatically manage and optimize data flows. [ABSTRACT FROM PUBLISHER]

Extract, Transform and Load (ETL) processes organized as workflows play an important role in data warehousing. As ETL workflows are usually complex, various ETL facilities have been developed to address their control-flow process modeling and execution control. To evaluate the quality of ETL facilities, Synthetic ETL workflow test cases, consisting of control-flow and data-flow aspects are needed to check ETL facility functionalities at construction time and to validate the correctness and performance of ETL facilities at run time. Although there are some synthetic workflow and data set test case generation approaches existed in literatures, little work is done to consider both aspects at the same time specifically for ETL workflow generators. To address this issue, this paper proposes a schema aware ETL workflow generator with which users can characterize their ETL workflows by various parameters and get ETL workflow test cases with control-flow of ETL activities, complied schemas and associated recordsets. Our generator consists of three steps. First, with type and ratio of individual activities and their connection characteristic parameter specification, the generator will produce ETL activities and form ETL skeleton which determine how generated activities are cooperated with each other. Second, with schema transformation characteristic parameter specification, e.g. ranges of numbers of attributes, the generator will resolve attribute dependencies and refine input/output schemas with complied attributes and their data types. In the last step, recordsets are generated following cardinality specifications. ETL workflows in specific patterns are produced in the experiment in order to show the ability of our generator. Also experiments to generate thousands of ETL workflow test cases in seconds have been done to verify the usability of the generator. [ABSTRACT FROM AUTHOR]

Abstract: Real-time and time-constrained applications programmed on many-core systems can suffer from unmet timing constraints even with correct-by-construction schedules. Such unexpected results are usually caused by unaccounted for delays due to resource sharing (e.g. the communication medium). In this paper we address the three main sources of unpredictable behaviors: First, we propose to use a deterministic Model of Computation (MoC), more specifically, the well-formed CSDF subset of process networks; Second, we propose a run-time management strategy of shared resources to avoid unpredictable timings; Third, we promote the use of a new scheduling policy, the so-said Self-Timed Periodic (STP) scheduling, to improve performance and decrease synchronization costs by taking into account resource sharing or resource constraints. This is a quantitative improvement above state-of-the-art scheduling policies which assumed fixed delays of inter-processor communication and did not take correctly into account subtle effects of synchronization. [Copyright &y& Elsevier]

This paper presents two case studies used to prove the validity of some data-flow mining algorithms. We proposed the data-flow mining algorithms because most part of mining algorithms focuses on the control-flow perspective. First case study uses event logs generated by an ERP system (Navision) after we set several trackers on the data elements needed in the process analyzed; while the second case study uses the event logs generated by YAWL system. We offered a general solution of data-flow model extraction from different data sources. In order to apply the data-flow mining algorithms the event logs must comply a certain format (using InputOutput extension). But to respect this format, a set of conversion tools is needed. We depicted the conversion tools used and how we got the data-flow models. Moreover, the data-flow model is compared to the control-flow model. [ABSTRACT FROM AUTHOR]

This paper describes a dynamically reconfigurable data-flow hardware architecture optimized for the computation of image and video. It is a scalable hierarchically organized parallel architecture that consists of data-flow clusters and finite-state machine (FSM) controllers. Each cluster contains various kinds of cells that are optimized for video processing. Furthermore, to facilitate the design process, we provide a C-like language for design specification and associated design tools. Some video applications have been implemented in the architecture to demonstrate the applicability and flexibility of the architecture. Experimental results show that the architecture, along with its video applications, can be used in many real-time video processing. [ABSTRACT FROM AUTHOR]

In this paper, we present a data-flow system which supports comparative analysis of time-dependent data and interactive simulation steering. The system creates data on-the-fly to allow for the exploration of different parameters and the investigation of multiple scenarios. Existing data-flow architectures provide no generic approach to handle modules that perform complex temporal processing such as particle tracing or statistical analysis over time. Moreover, there is no solution to create and manage module data, which is associated with alternative scenarios. Our solution is based on generic data-flow algorithms to automate this process, enabling elaborate data-flow procedures, such as simulation, temporal integration or data aggregation over many time steps in many worlds. To hide the complexity from the user, we extend the World Lines interaction techniques to control the novel data-flow architecture. The concept of multiple, special-purpose cursors is introduced to let users intuitively navigate through time and alternative scenarios. Users specify only what they want to see, the decision which data are required is handled automatically. The concepts are explained by taking the example of the simulation and analysis of material transport in levee-breach scenarios. To strengthen the general applicability, we demonstrate the investigation of vortices in an offline-simulated dam-break data set. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we present a methodology for optimizing complex datapath oriented digital circuits. An optimizer was developed based on the earlier development of an automatic circuit synthesizer that synthesizes hardware description language specifications based on available functional modules. A genetic algorithm is tailored to the problem of digital circuit optimization through the development of specific structures and procedures. In particular, a concise encoding of the circuit is developed that the genetic algorithm can manipulate. Specific crossover and mutation mechanisms are also developed to complement the functionality of the synthesizer. The searches are effected by altering module data type, hardware resource sharing, and module implementation version. A fitness function is derived that makes use of a number of optimization parameters to objectively evaluate each particular circuit. The features of each circuit are calculated and estimated during the analysis phase. [Copyright &y& Elsevier]

This paper is a general overview of the Skipper project, run at Blaise Pascal University between 1996 and 2002. The main goal of the Skipper project was to demonstrate the applicability of skeleton-based parallel programming techniques to the fast prototyping of reactive vision applications. This project has produced several versions of a full-fledged integrated parallel programming environment (PPE). These PPEs have been used to implement realistic vision applications, such as road following or vehicle tracking for assisted driving, on embedded parallel platforms embarked on semi-autonomous vehicles. All versions of Skipper share a common front-end and repertoire of skeletons––presented in previous papers––but differ in the techniques used for implementing skeletons. This paper focuses on these implementation issues, by making a comparative survey, according to a set of four criteria (efficiency, expressivity, portability, predictability), of these implementation techniques. It also gives an account of the lessons we have learned, both when dealing with these implementation issues and when using the resulting tools for prototyping vision applications. [Copyright &y& Elsevier]