Binqi Sun

Binqi Sun

Auto-generated profile, based on publicly available information

Binqi Sun

Technical University of Munich

Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
5 January 2024 in IEEE Transactions on Computers
Verified
Journal Article
Closed access
BSBinqi Sun
Binqi Sun
MTMirco Theile
Mirco Theile
ZQZiyuan Qin
Ziyuan Qin
DBDaniele Bernardini
Daniele Bernardini
DRDebayan Roy
Debayan Roy
MCMarco Caccamo
Marco Caccamo
Directed acyclic graph (DAG) tasks are currently adopted in the real-time domain to model complex applications from the automotive, avionics, and industrial domains that implement their functionalities through chains of intercommunicating tasks. This paper studies the problem of scheduling real-time DAG tasks by presenting a novel schedulability test based on the concept of trivial schedulability . Using this schedulability test, we propose a new DAG scheduling framework ( edge generation scheduling—EGS ) that attempts to minimize the DAG width by iteratively generating edges while guaranteeing the deadline constraint. We study how to efficiently solve the problem of generating edges by developing a deep reinforcement learning algorithm combined with a graph representation neural network to learn an efficient edge generation policy for EGS. We evaluate the effectiveness of the proposed algorithm by comparing it with state-of-the-art DAG scheduling heuristics and an optimal mixed-integer linear programming baseline. Experimental results show that the proposed algorithm outperforms the state-of-the-art by requiring fewer processors to schedule the same DAG tasks. https://github.com/binqi-sun/egs

18 August 2021
Verified
Conference Paper
Open access
CLChuan Luo
Chuan Luo
BSBinqi Sun
Binqi Sun
BQBo Qiao
Bo Qiao
JCJunjie Chen
Junjie Chen
Hongyu ZhangHongyu Zhang
Hongyu Zhang
DZDongmei Zhang
Dongmei Zhang
There has been a rapidly increasing demand for developing highly configurable software systems, which urgently calls for effective testing methods. In practice, t-wise coverage has been widely recognized as a useful metric to evaluate the quality of a test suite for testing highly configurable software systems, and achieving high t-wise coverage is important for ensuring test adequacy. However, state-of-the-art methods usually cost a fairly long time to generate large test suites for high pairwise coverage (i.e., 2-wise coverage), which would lead to ineffective and inefficient testing of highly configurable software systems. In this paper, we propose a novel local search based sampling approach dubbed LS-Sampling for achieving high t-wise coverage. Extensive experiments on a large number of public benchmarks, which are collected from real-world, highly configurable software systems, show that LS-Sampling achieves higher 2-wise and 3-wise coverage than the current state of the art. LS-Sampling is effective, since on average it achieves the 2-wise coverage of 99.64% and the 3-wise coverage of 97.87% through generating a small test suite consisting of only 100 test cases (90% smaller than the test suites generated by its state-of-the-art competitors). Furthermore, LS-Sampling is efficient, since it only requires an average execution time of less than one minute to generate a test suite with high 2-wise and 3-wise coverage.

1 May 2019 in Computers & Industrial Engineering
Verified
Journal Article
Closed access
BSBin-Qi Sun
Bin-Qi Sun
LWLing Wang
Ling Wang

12 June 2020 in Complex & Intelligent Systems
Verified
Journal Article
Open access
PDF file
BSBin-Qi Sun
Bin-Qi Sun
LWLing Wang
Ling Wang
Robotic assembly lines are widely used in manufacturing industries. The robotic assembly line balancing (RALB) problem aims to balance the workloads among different workstations and optimize the assembly line efficiency. This paper addresses a particular type of RALB problem, which minimizes the assembly line cycle time by determining the task and robot assignment in each workstation under precedence constraints. To solve the problem, we present an effective hybrid algorithm fusing the estimation of distribution algorithm and branch-and-bound (B&B) based knowledge. A problem-specific probability model is designed to describe the probabilities of each task being assigned to different workstations. Based on the probability model, an incremental learning method is developed and a sampling mechanism with B&B based knowledge is proposed to generate new feasible solutions. The fuse of B&B based knowledge is able to reduce the search space of EDA while focusing the search on the promising area. To enhance the exploitation ability, a problem-specific local search is developed based on the critical workstation to further improve the quality of elite solutions. The computational complexity of the proposed algorithm is analyzed, and the effectiveness of the B&B based knowledge and the problem-specific local search is demonstrated through numerical experiments. Moreover, the performance of the proposed algorithm is compared with existing algorithms on a set of widely-used benchmark instances. Comparative results demonstrate the effectiveness and efficiency of the proposed algorithm.

31 December 2024 in ACM Transactions on Software Engineering and Methodology
Verified
Journal Article
Open access
CLChuan Luo
Chuan Luo
JSJianping Song
Jianping Song
QZQiyuan Zhao
Qiyuan Zhao
BSBinqi Sun
Binqi Sun
JCJunjie Chen
Junjie Chen
CHChunming Hu
Chunming Hu
To meet the increasing demand for customized software, highly configurable systems become essential in practice. Such systems offer many options to configure, and ensuring the reliability of these systems is critical. A widely used evaluation metric for testing these systems is \(t\) -wise coverage, where \(t\) represents testing strength, and its value typically ranges from 2 to 6. It is crucial to design effective and efficient methods for generating test suites that achieve high \(t\) -wise coverage. However, current state-of-the-art methods need to generate large test suites for achieving high \(t\) -wise coverage. In this work, we propose a novel method called LS-Sampling-Plus that can efficiently generate test suites with high \(t\) -wise coverage for \(2\leq t\leq 6\) while being smaller in size compared to existing state-of-the-art methods. LS-Sampling-Plus incorporates many core algorithmic techniques, including two novel scoring functions, a dynamic mechanism for updating sampling probabilities, and a validity-guaranteed systematic search method. Our experiments on various practical benchmarks show that LS-Sampling-Plus can achieve higher \(t\) -wise coverage than current state-of-the-art methods, through building a test suite of the same size. Moreover, our evaluations indicate the effectiveness of all core algorithmic techniques of LS-Sampling-Plus . Furthermore, LS-Sampling-Plus exhibits better scalability and fault detection capability than existing state-of-the-art methods.

28 June 2024 in Real-Time Systems
Verified
Journal Article
Open access
PDF file
BSBinqi Sun
Binqi Sun
TKTomasz Kloda
Tomasz Kloda
SGSergio Arribas Garcia
Sergio Arribas Garcia
GGGiovani Gracioli
Giovani Gracioli
MCMarco Caccamo
Marco Caccamo
Cache partitioning is a technique to reduce interference among tasks running on the processors with shared caches. To make this technique effective, cache segments should be allocated to tasks that will benefit the most from having their data and instructions stored in the cache. The requests for cached data and instructions can be retrieved faster from the cache memory instead of fetching them from the main memory, thereby reducing overall execution time. The existing partitioning schemes for real-time systems divide the available cache among the tasks to guarantee their schedulability as the sole and primary optimization criterion. However, it is also preferable, particularly in systems with power constraints or mixed criticalities where low- and high-criticality workloads are executing alongside, to reduce the total cache usage for real-time tasks. Cache minimization as part of design space exploration can also help in achieving optimal system performance and resource utilization in embedded systems. In this paper, we develop optimization algorithms for cache partitioning that, besides ensuring schedulability, also minimize cache usage. We consider both preemptive and non-preemptive scheduling policies on single-processor systems with fixed- and dynamic-priority scheduling algorithms (Rate Monotonic (RM) and Earliest Deadline First (EDF), respectively). For preemptive scheduling, we formulate the problem as an integer quadratically constrained program and propose an efficient heuristic achieving near-optimal solutions. For non-preemptive scheduling, we combine linear and binary search techniques with different fixed-priority schedulability tests and Quick Processor-demand Analysis (QPA) for EDF. Our experiments based on synthetic task sets with parameters from real-world embedded applications show that the proposed heuristic: (i) achieves an average optimality gap of 0.79% within 0.1× run time of a mathematical programming solver and (ii) reduces average cache usage by 39.15% compared to existing cache partitioning approaches. Besides, we find that for large task sets with high utilization, non-preemptive scheduling can use less cache than preemptive to guarantee schedulability.