Open Access Issue
Efficient Algorithm for the k-Means Problem with Must-Link and Cannot-Link Constraints
Tsinghua Science and Technology 2023, 28 (6): 1050-1062
Published: 28 July 2023
Abstract PDF (5 MB) Collect

Constrained clustering, such as k-means with instance-level Must-Link (ML) and Cannot-Link (CL) auxiliary information as the constraints, has been extensively studied recently, due to its broad applications in data science and AI. Despite some heuristic approaches, there has not been any algorithm providing a non-trivial approximation ratio to the constrained k-means problem. To address this issue, we propose an algorithm with a provable approximation ratio of O(logk) when only ML constraints are considered. We also empirically evaluate the performance of our algorithm on real-world datasets having artificial ML and disjoint CL constraints. The experimental results show that our algorithm outperforms the existing greedy-based heuristic methods in clustering accuracy.

Open Access Issue
Data Fusion with Genetic Algorithm Based Lifetime Prediction for Dependable Multi-Processor System-on-Chips
Tsinghua Science and Technology 2023, 28 (6): 1041-1049
Published: 28 July 2023
Abstract PDF (7.2 MB) Collect

With the prevalence of big-data technology, intricate, nanoscale Multi-Processor System-on-Chips (MP-SoCs) have been used in various safety-critical applications. However, with no extra countermeasures taken, this widespread use of MP-SoCs can lead to an undesirable decrease in their dependability. This study presents a promising approach using a group of Embedded Instruments (EIs) inside a processor core for health monitoring. Multiple health monitoring datasets obtained from the employed EIs are sampled and collated via the implemented experiment and thereafter used for conducting its remaining useful lifetime prognostics. This enables MP-SoCs to undertake preventive self-repair, thus realizing a zero mean downtime system and ensuring improved dependability. In addition, a principal component analysis based algorithm is designed for realizing the EI data fusion. Subsequently, a genetic algorithm based degradation optimization is employed to create a lifetime prediction model with respect to the processor.

Open Access Issue
A Two-Stage Method for Routing in Field-Programmable Gate Arrays with Time-Division Multiplexing
Tsinghua Science and Technology 2022, 27 (6): 902-911
Published: 21 June 2022
Abstract PDF (2.7 MB) Collect

Emerging applications widely use field-programmable gate array (FPGA) prototypes as a tool to verify modern very-large-scale integration (VLSI) circuits, imposing many problems, including routing failure caused by the limited number of connections among blocks of FPGAs therein. Such a shortage of connections can be alleviated through time-division multiplexing (TDM), by which multiple signals sharing an identical routing channel can be transmitted. In this context, the routing quality dominantly decides the performance of such systems, proposing the requirement of minimizing the signal delay between FPGA pairs. This paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support, aiming to minimize the maximum TDM ratio. The algorithm consists of two major stages: (1) A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees. (2) A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio constraints. Experiments were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works, and the results manifest that our method achieves a better TDM ratio in comparison.

Total 3