With the widespread use of location-tracking technologies, large volumes of trajectory data are continuously generated. Trajectory similarity computation is a core task in trajectory mining with broad applications. However, existing methods still face two key challenges: (1) the difficulty of balancing efficiency and representation quality, and (2) the reliance on a single training paradigm, which limits the ability to capture both pairwise similarity and batch-level coherence. To address these challenges, we propose a trajectory similarity computation framework named TrajAgg. Specifically, our framework incorporates a novel Aggregation Transformer that efficiently aggregates GPS and grid features through two stages of direct interaction and enhances the expressiveness of the resulting trajectory embeddings. In addition, by integrating two distinct training paradigms, our model captures both fine-grained pairwise relationships and global structural consistency. We further analyze its effectiveness from the perspective of mutual information. Extensive experiments on three publicly available datasets show that TrajAgg consistently outperforms state-of-the-art baselines. Our method achieves average improvements of 15.11%, 16.49%, 10.41%, and 40.15% in HR@1 under four distance measures across three datasets, respectively.

As user behavior data becomes increasingly scattered across different platforms, achieving cross-domain knowledge fusion while preserving privacy has become a critical issue in recommender systems. Existing Privacy-Preserving Cross-Domain Recommendation (PPCDR) methods usually rely on overlapping users or items as a bridge, making them inapplicable to non-overlapping scenarios. They also suffer from limitations in the collaborative modeling of global and local semantics. To this end, this paper proposes a Federated Cross-domain Recommendation method with deep knowledge Fusion (FedCRF). Using textual semantics as the cross-domain bridge, FedCRF achieves cross-domain knowledge transfer via federated semantic learning under the non-overlapping scenario. Specifically, FedCRF constructs global semantic clusters on the server side to extract shared semantic information, and designs a Fine-Grained Semantic Adaptation and Transfer (FGSAT) module on the client side to dynamically adapt to local data distributions and alleviate cross-domain distribution shift. Meanwhile, it builds a semantic graph based on textual features to learn representations that integrate both structural and semantic information, and introduces contrastive learning constraints between global and local semantic representations to enhance semantic consistency and promote deep knowledge fusion. In this framework, only item semantic representations are shared, while user interaction data remains locally stored, effectively mitigating privacy leakage risks. Experimental results on multiple real-world datasets show that FedCRF significantly outperforms existing methods in terms of Recall@20 and NDCG@20, validating its effectiveness and superiority in non-overlapping cross-domain recommendation scenarios.

MicroRNAs (miRNAs) are small non-coding RNAs orchestrating regulatory networks through sequence-specific target recognition. Understanding miRNA-disease correlations is crucial as high-throughput sequencing data growth outpaces experimental validation, necessitating computational approaches for association discovery. Existing frameworks model miRNA-disease interactions as uniform binary relationships, overlooking semantic diversity in different association mechanisms. We propose BKAMDA (MiRNA-Disease Associations prediction Based on Knowledge-Awareness), a novel knowledge-aware model for predicting miRNA-disease associations. Unlike existing methods learning only from miRNA-disease networks, BKAMDA leverages knowledge graphs to delineate distinct association types. By simulating informational propagation within knowledge graphs across diverse miRNA-disease relationships, the model investigates latent connections across various relationship types. Comparative analysis with competitive baselines using real-world experimentally validated datasets demonstrates excellent performance across multiple metrics. Three disease case studies further confirm model accuracy and effectiveness for precision medicine applications. Our knowledge-aware approach significantly advances miRNA-disease association prediction by capturing semantic diversity in biological interactions.

Traffic prediction is critical for optimizing travel scheduling and enhancing public safety, yet the complex spatial and temporal dynamics within traffic data present significant challenges for accurate forecasting. In this paper, we introduce a novel model, the Spatiotemporal-aware Trend-Seasonality Decomposition Network (STDN). This model begins by constructing a dynamic graph structure to represent traffic flow and incorporates novel spatio-temporal embeddings to jointly capture global traffic dynamics. The representations learned are further refined by a specially designed trend-seasonality decomposition module, which disentangles the trend-cyclical component and seasonal component for each traffic node at different times within the graph. These components are subsequently processed through an encoder-decoder network to generate the final predictions. Extensive experiments conducted on real-world traffic datasets demonstrate that STDN achieves superior performance with remarkable computation cost. Furthermore, we have released a new traffic dataset named JiNan, which features unique inner-city dynamics, thereby enriching the scenario comprehensiveness in traffic prediction evaluation.

Trajectory-user linking (TUL) aims to match anonymous trajectories to the most likely users who generated them, offering benefits for a wide range of real-world spatio-temporal applications. However, existing TUL methods are limited by high model complexity and poor learning of the effective representations of trajectories, rendering them ineffective in handling large-scale user trajectory data.In this work, we propose a novel Scalable Trajectory-User Linking with dual-stream representation networks for large-scale TUL problem, named ScaleTUL Specifically, ScaleTUL generates two views using temporal and spatial augmentations to exploit supervised contrastive learning framework to effectively capture the irregularities of trajectories. In each view, a dual-stream trajectory encoder consisting of a long-term encoder and a short-term encoder is designed to learn the unified representations of trajectories that fuses different temporal-spatial dependencies. Then, a TUL layer is used to associate the trajectories with the corresponding users in the representation space using a two-stage training model.Experimental results on check-in mobility datasets from three real-world cities and the nationwide U.S. demonstrate the superiority of ScaleTUL over state-of-the-art baselines for large-scale TUL tasks.

Multivariate time series forecasting is a critical focus across many fields. Existing transformer-based models have overlooked the explicit modeling of inter-variable correlations. Similarly, the graph-based methods have also failed to address the dynamic nature of multivariate correlations and the noise in correlation modeling. To overcome these challenges, we propose a novel Dynamic Graph Learning Guided Multi-Scale Transformer (DGraFormer) for multivariate time series forecasting. Specifically, our method consists of two main components: Dynamic correlation-aware graph Learning (DCGL) and multi-scale temporal transformer (MTT). The former aims to capture dynamic correlations across different time windows, filters out noise, and selects key weights to guide the aggregation of relevant feature representations. The latter can effectively extract temporal patterns from patch data at varying scales. Finally, the proposed method can capture rich local correlation graph structures and multi-scale global temporal features. Experimental results demonstrate that DGraformer significantly outperforms existing state-of-the-art models on ten real-world datasets, achieving the best performance across multiple evaluation metrics. The source code of our model is available at \url{https://anonymous.4open.science/r/DGraFormer}.

Side-channel-based Deep Neural Network (DNN) model stealing has become a major concern with the advent of learning-based attacks. In respond to this threat, defence mechanisms have been presented to obfuscate the DNN execution, making it difficult to infer the correlation between side-channel information and DNN architecture. However, state-of-the-art (SOTA) DNN obfuscation is time-consuming, requires expert-level changes in existing DNN compilers (e.g., Tensor Virtual Machine (TVM)), and often relies on prior knowledge of the attack models. In this work, we study the impact of various obfuscation levels on the defence effectiveness, and present a streamlined DNN obfuscation process that is extremely fast and is agnostic to any attack models. Our study reveals that by just modifying the scheduling of DNN operations on the GPU, we can achieve comparable defense performance as the SOTA in an attack agnostic manner. We also propose a simple algorithm that determines an effective scheduling configuration for mitigating DNN model stealing at a fraction of a time required by SOTA obfuscation methods. Our method can be easily integrated into existing DNN compilers as a security feature, even by non-experts, to protect their DNN against side-channel attacks.

Deep neural network (DNN) intellectual property (IP) models must be kept undisclosed to avoid revealing trade secrets. Recent works have devised machine learning techniques that leverage on side-channel information leakage of the target platform to reverse engineer DNN architectures. However, these works fail to perform successful attacks on DNNs that have undergone performance optimizations (i.e., operator fusion) using DNN compilers, e.g., Apache tensor virtual machine (TVM). We propose a two-phase attack framework to infer the layer sequences of optimized DNNs through side-channel information leakage. In the first phase, we use a recurrent network with multihead attention components to learn the intra and interlayer fusion patterns from GPU traces of TVM-optimized DNNs, in order to accurately predict the operation distribution. The second phase uses a model to learn the run-time temporal correlations between operations and layers, which enables the prediction of layer sequence. An encoding strategy is proposed to overcome the convergence issues faced by existing learning-based methods when inferring the layer sequences of optimized DNNs. Extensive experiments show that our learning-based framework outperforms state-of-the-art DNN model extraction techniques. Our framework is also the first to effectively reverse engineer both convolutional neural networks (CNNs) and recurrent neural networks (RNNs) using side-channel leakage.

Multimodal public transport networks (MMPTNs) in modern cities are becoming increasingly complex. This makes finding optimal journey routes challenging due to a large number of transfer options that need to be properly considered. Furthermore, the complexity of the problem is compounded when multiple conflicting travel criteria are considered (e.g., travel time, walking distance, travel fare, etc.). This paper proposes a transfer graph (TG) model to explore the transfer opportunities of the MMPTN to support efficient journey route planning. TG considers all possible transfer opportunities, while employing a representative mechanism to optimize the TG structure that supports efficient route planning algorithms. Based on the proposed TG, we develop two exact algorithms to search the Pareto-optimal solutions for multi-criteria journey planning (MCJP) over the MMPTN. The first algorithm runs faster by eliminating many partial solutions at an early stage, which is more suited for lowering computation time at the expense of marginal degradation in output quality. In contrast, the second algorithm provides a more dependable solution by incorporating accurate journey time prediction that caters to the evolving traffic conditions. We also develop techniques to accelerate the TEDE and TEAE algorithms. Experiments on real-world public transport networks and traffic data demonstrate the effectiveness of our approach for MCJP. Experiment results also reveal interesting insights on the impact of the TOs, number of transfers, and number of travel criteria on MCJP algorithms, which can contribute to better public transportation planning.

Transport mode identification (TMI), which infers the travel modes of user trajectories, is essential to facilitate an understanding of urban mobility patterns and passengers’ choice behaviors with the goal of improving urban transportation systems. To achieve higher accuracy, existing TMI methods usually rely on mobility features obtained from densely sampled GPS trajectory points (e.g. 1 second per GPS point) or data measurements of additional inertial measurement unit (IMU) sensors (e.g. accelerometer, gyroscope, rotation vector). However, these lead to high energy consumption of the users’ mobile devices. In this paper, we propose a novel deep learning framework, Multi-Scale Attributes Attention (MSAA) model, to extract discriminating trajectory features from GPS data only, without the need to increase its sampling rate. The proposed model first partitions the trajectories into different scales and extract the latent representation of local attributes at each scale. The MSAA model relies on Convolutional Neural Network (CNN) to capture the spatial correlation of different trajectory segments, and utilizes attention mechanism to select the most suitable local attributes on the different trajectory scales that can effectively characterize the various transport modes. Since the learned latent local attributes are significantly different from the global features (e.g. average/min/max travel speeds which are measurable quantities), an ensemble model based on Neural Decision Forest (NDF) is employed to fuse the heterogeneous features consisting of both measurable quantities and non-measurable elements for determining the transport mode. Experiments on real-world datasets demonstrate the competitive performance of the proposed approach compared to several state-of-the-art baselines, with average improvements in accuracy ranging from 0.76% to 6.4%. In addition, the proposed multi-scale local attributes well complement the global features. Our results show that by incorporating the local attributes, the detection performance improved by 2.3% on average compared to using only global features.

Traffic congestion has become a global concern due to continuous increase in traffic demand and limited road capacity. The ability to predict traffic congestion propagation, which depicts the spatiotemporal evolution of the congestion scenario, is essential for developing smart traffic management systems and enabling road users to make informed route choices. In this work, we study the behavior of congestion propagation at the road segment level, and leverage this to develop a novel machine learning framework that characterizes and predicts the congestion evolution among different road segments in the traffic network. In particular, our framework can infer the likelihood of congestion propagation between any pair of road segments through single or multiple propagation paths. The proposed framework relies on a network embedding module to learn a representation for each road segment, and a propagation model which calculates the congestion propagation likelihood based on the learned representations. Specifically, an asymmetric embedding of local proximity and global tendency (AE-LPGT) is relied upon for learning low dimension embeddings of the road segments which incorporate various realistic properties of congestion propagations, such as the local proximity property, global propagation tendency, and asymmetric transitivity of congestion propagations. Experimental results with Singapore traffic data show that our method significantly outperforms the state-of-the-art, and the congestion propagation properties in our embeddings have significant impact on the prediction performance.

Many efforts are devoted to predicting congestion evolution using propagation patterns that are mined from historical traffic data. However, the prediction quality is limited to the intrinsic properties that are present in the mined patterns. In addition, these mined patterns frequently fail to sufficiently capture many realistic characteristics of true congestion evolution (e.g., asymmetric transitivity, local proximity). In this paper, we propose a representation learning framework to characterize and predict congestion evolution between any pair of road segments (connected via single or multiple paths). Specifically, we build dynamic attributed networks (DAN) to incorporate both dynamic and static impact factors while preserving dynamic topological structures. We propose a Deep Meta Learning Model (DMLM) for learning representations of road segments which support accurate prediction of congestion evolution. DMLM relies on matrix factorization techniques and meta-LSTM modules to exploit temporal correlations at multiple scales, and employ meta-Attention modules to merge heterogeneous features while learning the time-varying impacts of both dynamic and static features. Compared to all state-of-the-art methods, our framework achieves significantly better prediction performance on two congestion evolution behaviors (propagation and decay) when evaluated using real-world dataset.

Recovering keys ranked in very deep candidate space efficiently is a very important but challenging issue in side-channel attacks (SCAs). State-of-the-art collision-optimized divide-and-conquer attacks (CODCAs) extract collision information from a collision attack to optimize the key recovery of a divide-and-conquer attack, and transform the very huge guessing space to a much smaller collision space. However, the inefficient collision detection makes them time consuming. The very limited collisions exploited and large performance difference between the collision attack and the divide-and-conquer attack in CODCAs also prevent their application in much larger spaces. In this article, we propose a Minkowski distance enhanced collision attack (MDCA) with performance closer to template attack (TA) compared to traditional correlation-enhanced collision attack (CECA), thus making the optimization more practical and meaningful. Next, we build a more advanced CODCA named full-collision chain (FCC) from TA and MDCA to exploit all collisions. Moreover, to minimize the thresholds while guaranteeing a high success probability of key recovery, we propose a fault-tolerant scheme to optimize FCC. The full key is divided into several big “blocks,” on which a fault-tolerant vector (FTV) is exploited to flexibly adjust its chain space. Finally, guessing theory is exploited to optimize thresholds determination and search order of subkeys. Experimental results show that FCC notably outperforms the existing CODCAs.

Several combined attacks have shown promising results in recovering cryptographic keys by introducing collision information into divide-and-conquer attacks to transform a part of the best key candidates within given thresholds into a much smaller collision space. However, these Collision-Optimized Divide-and-Conquer Attacks (CODCAs) uniformly demarcate the thresholds for all sub-keys, which is unreasonable. Moreover, the inadequate exploitation of collision information and backward fault tolerance mechanisms of CODCAs also lead to low attack efficiency. Finally, existing CODCAs mainly focus on improving collision detection algorithms but lack theoretical basis. We exploit Correlation-Enhanced Collision Attack (CECA) to optimize Template Attack (TA). To overcome the above-mentioned problems, we first introduce guessing theory into TA to enable the quick estimation of success probability and the corresponding complexity of key recovery. Next, a novel Multiple-Differential mechanism for CODCAs (MD-CODCA) is proposed. The first two differential mechanisms construct collision chains satisfying the given number of collisions from several sub-keys with the fewest candidates under a fixed probability provided by guessing theory, then exploit them to vote for the remaining sub-keys. This guarantees that the number of remaining chains is minimal, and makes MD-CODCA suitable for very high thresholds. Our third differential mechanism simply divides the key into several large non-overlapping “blocks” to further exploit intra-block collisions from the remaining candidates and properly ignore the inter-block collisions, thus facilitating the later key enumeration. The experimental results show that MD-CODCA significantly reduces the candidate space and lowers the complexity of collision detection, without considerably reducing the success probability of attacks.

Abstract Hardware/software (HW/SW) partitioning, that decides which components of an application are implemented in hardware and which ones in software, is a crucial step in embedded system design. On modern heterogeneous embedded system platform, each component of application can typically have multiple feasible configurations/implementations, trading off quality aspects (e.g. energy consumption, completion time) with usage for various types of resources. This provides new opportunities for further improving the overall system performance, but few works explore the potential opportunity by incorporating the multiple choices of hardware implementation in the partitioning process. This paper proposes three algorithms for multiple-choice HW/SW partitioning of tree-shape task graph on multiple processors system on chip (MPSoC) with the objective of minimizing execution time, while meeting area constraint. Firstly, an efficient heuristic algorithm is proposed to rapidly generate an approximate solution. The obtained solution produced by the first algorithm is then further refined by a customized Tabu search algorithm. We also propose a dynamic programming algorithm to calculate the exact solutions for relatively smaller scale instances. Simulation results show that the proposed heuristic algorithm is able to quickly generate good approximate solutions, and the solutions become very close to the exact solutions after refined by the proposed Tabu search algorithm, in comparison to the exact solutions produced by the dynamic programming algorithm.

By introducing collision information into divide-and-conquer attacks, several existing works transform the original candidate space, which may be too large to enumerate, into a significantly smaller collision space, thus making key recovery possible. However, the inefficient collision detection algorithms and fault tolerance mechanisms make them time-consuming and their success rate low. Moreover, they may still leave very huge chain spaces that makes it difficult for key recovery. In this article, we exploit collision attack to optimize Template Attack (TA), and propose a Lightweight Collision Detection (LCD) algorithm. The proposed method exploits a jump detection mechanism to efficiently reduce the repetitive collision detections on chains with the same prefix sub-chains. We then introduce guessing theory to reorder the collision detection of the sub-keys according to their guessing lengths, and provide us with an evaluation tool. Finally, we design a highly efficient fault tolerance mechanism for our LCD to allow flexible thresholds adjustment, and further optimize sieving mechanism to efficiently extract the best chains with the largest number of collisions. Experimental results fully demonstrate LCD's superiority.

The first-mile transportation provides a transit service using ridesharing-based vehicles, e.g., feeder buses, for passengers to travel from their homes, workplaces, or public institutions to the nearest public transportation depots (rapid-transit metro or appropriated bus stations) which are located beyond comfortable walking distance. This paper studies the vehicle routing problem (VRP) for the first-mile transportation, which aims at finding the optimal travel routes for a vehicle fleet to deliver passengers from their doorstep to the depots, where the passengers can continue their journeys using fixed-route buses or trains. We focus on the Peak-Hour VRP (PHVRP) for a limited vehicle fleet capacity to serve a large volume of travel requests, with the aim of maximizing the number of served passengers. The PHVRP generalizes the VRP with time window by considering multiple alternative depots for each travel request, such that a request is satisfied if the passenger is taken to one of his/her nearest depots. We formally formulate the PHVRP with constraints on vehicle capacity, pickup time windows, and quality of service regarding riding time, where a novel trip-based constraint model is used. We proposed an ant-colony optimization algorithm for the PHVRP, which is initialized with pheromone information that jointly considers the temporal-spatial distance as well as depot similarity among different travel requests. We introduced a novel scheme (called trip-by-trip scheme) to construct the travel routes by repeatedly forming a single trip for the vehicle with earliest end time until no vehicle can accept any more trips. In constructing a single trip, the algorithm intelligently decides whether or not to end the trip instead of taking more passengers. The effectiveness of the proposed methods is evaluated by comparing with optimal solutions on small size instances and with heuristic solutions on large-size instances, using road network in Singapore and synthetic travel requests that are generated based on real bus travel demands.

The adoption of large-scale MPSoCs and the globalization of the IC design flow give rise to two major concerns: high power density due to continuous technology scaling and security due to the untrustworthiness of the third-party intellectual property (3PIP) cores. However, little work has been undertaken to consider these two critical issues jointly during the design stage. In this paper, we propose a design methodology that minimizes the energy consumption while simultaneously protecting the MPSoC against the effects of hardware trojans. The proposed methodology consists of three main stages: 1) Task scheduling to introduce core diversity in the MPSoC in order to detect the presence of malicious modifications in the cores, or mute their effects at runtime, 2) Vendor assignment to the cores using a novel heuristic that chooses vendor-specific cores with operating speed that minimizes the total energy consumption of the MPSoC, and 3) Explore optimization opportunities for further energy savings by minimizing idle periods on the cores, which are caused by the inter-task data dependencies. Experimental results show that our solutions consume only 1/3 energy of existing solutions without increasing schedule length while satisfying the security constraints.

Accurate bus travel speed prediction can lead to improved urban mobility by enabling passengers to reliably plan their trips in advance and traffic administrators to manage the bus operations more effectively. However, the increasing complexity of public transportation networks pose a significant challenge to existing prediction methods as the bus operations are affected by numerous factors such as varying traffic conditions, tight bus operation schedules, wide-ranging travel demands, frequent accelerations/decelerations at bus stops, delays at intersections, etc. This paper aims to achieve accurate bus speed prediction by identifying important intrinsic and extrinsic features that impact the bus speed, and their significance in specific situations. We propose to jointly incorporate multiple feature components that provide discriminating information to train the prediction model by exploring the spatial correlation, temporal correlation, as well as contextual information (e.g. road characteristics and weather conditions). In particular, we introduce an attribute-driven attention network model to integrate the feature components, which considers the heterogeneous influence of different feature components on bus speed and dynamically assigns weights to the learned latent features based on specific traffic situations. Extensive experiments using real bus travel data involving 42 bus services show that our proposed method outperforms six well-known methods.

Abstract The task offloading problem, which aims to balance the energy consumption and latency for Mobile Edge Computing (MEC), is still a challenging problem due to the dynamic changing system environment. To reduce energy while guaranteeing delay constraint for mobile applications, we propose an access control management architecture for 5G heterogeneous network by making full use of Base Station’s storage capability and reusing repetitive computational resource for tasks. For applications that rely on real-time information, we propose two algorithms to offload tasks with consideration of both energy efficiency and computation time constraint. For the first scenario, i.e. the rarely changing system environment, an optimal static algorithm is proposed based on dynamic programming technique to get the exact solution. For the second scenario, i.e. the frequently changing system environment, a two-stage online algorithm is proposed to adaptively obtain the current optimal solution in real time. Simulation results demonstrate that the exact algorithm in the first scenario runs 4 times faster than the enumeration method. In the second scenario, the proposed online algorithm can reduce the energy consumption and computation time violation rate by 16.3% and 25% in comparison with existing methods.

Accurate travel-time prediction of public transport is essential for reliable journey planning in urban transportation systems. However, existing studies on bus travel-/arrival-time prediction often focus only on improving the prediction accuracy of a single bus trip. This is inadequate in modern public transportation systems, where a bus journey usually consists of multiple bus trips. In this paper, we investigate the problem of travel-time prediction for bus journeys that takes into account a passenger's riding time on multiple bus trips, and also his/her waiting time at transfer points (interchange stations or bus stops). A novel framework is proposed to separately predict the riding and waiting time of a given journey from multiple datasets (i.e., historical bus trajectories, bus route, and road network), and combining the results to form the final travel-time prediction. We empirically determine the impact factors of bus riding times and develop a long short-term memory model that can accurately predict the riding time of each segment of the bus lines/routes. We also demonstrate that the waiting time at transfer points significantly impacts the total journey travel time, and estimating the waiting time is non-trivial as we cannot assume a fixed distribution waiting time. In order to accurately predict the waiting time, we introduce a novel interval-based historical average method that can efficiently address the correlation and sensitivity issues in waiting time prediction. Experiments on real-world data show that the proposed method notably outperforms six baseline approaches for all the scenarios considered.

Integrity trees are widely used in computer systems to prevent replay, splicing, and spoofing attacks on memories. Such mechanisms incur excessive performance and energy overhead. We propose a memory authentication framework that combines architecture-specific optimizations of the integrity tree with mechanisms that enable it to restructure at runtime based on memory access patterns. The integrity tree structure is customized based on the cache configuration in order to minimize the performance and energy overhead through speculative authentication. At runtime, the tree nodes that are accessed more frequently will be dynamically shifted closer to the root such that fewer levels of the tree are accessed during authentication. The framework is simulated with Multi2Sim and compared with other existing mechanisms [i.e., tamper-evident counter (TEC) tree and ASSURE] to demonstrate its performance and energy benefits. Experimental results using benchmarks from SPEC-CPU2006, SPLASH-2, and PARSEC show that the proposed dynamic integrity tree leads to an average reduction in instruction per cycle of 13% and 10% over TEC tree and ASSURE, respectively. The corresponding average reduction in authentication time is 30% and 20%, respectively. We show that the proposed framework facilitates the selection of a processor with a smaller cache size such that the energy consumption is reduced without sacrificing performance.

Memory authentication techniques often employ an integrity tree as a countermeasure against replay, spoofing and splicing attacks. However, the balanced memory integrity trees used in existing approaches lead to excessive memory access overheads for runtime verification. In this paper, we propose a framework to dynamically construct a customized integrity tree based on the data access patterns to reduce the overhead of runtime verification. The proposed framework can adapt the memory integrity tree structure at runtime such that the nodes that correspond to frequently accessed data are placed closer to the root. We validated the effectiveness of our approach on the Altera NIOS II processor with an external DRAM. Experimental results based on applications from widely used CHStone and SNU Real-Time benchmarks demonstrate that the proposed approach can lead to an average performance gain of 30% compared to the conventional means of using balanced memory integrity trees. In addition, to preserve data confidentiality, we implemented the encryption/decryption operations using custom instructions on the NIOS II processor to notably reduce the overall overhead of memory security.

A critical issue in data replication is to wisely place data replicas which involves identifying the best possible nodes to duplicate data. Facing dynamics of data requests, this paper investigates the problem of replica placement and update in tree networks, where part of nodes have pre-existing replicas. We aim to develop efficient algorithms to accelerate the replica placement and update without causing obvious degradation in solution quality via reusing pre-existing replicas. Firstly, an efficient heuristic algorithm GRP is proposed to quickly place replicas when users change their requests dynamically, under the Closest policy where a client must be served by the closest server. Then, a Tabu search algorithm TSRP is customized to further refine the solution obtained by GRP. Furthermore, we propose a heuristic algorithm MPFSF for the replica placement and update problem, under the Multiple policy where requests of a client are served by multiple servers. Simulation results show that, GRP and TSRP can accelerate existing dynamic programming algorithm by 87.97% while quality degradation is bounded by 2.49%. MPFSF can achieve the best improvement for about 84.6% than existing heuristic algorithm.

Modern FPGAs integrate multi-million logic resources that allow the realization of increasingly large designs. However, state-of-the-art simulated annealing based CAD tools for FPGA suffer from long runtime, poor performance and sub-optimal routing and placement decisions, especially for large applications, leading to less energy efficient designs. In this paper, we present a partitioning methodology that divides large application into smaller subsystems based on the communication frequency between these subsystems. We leverage the existing CAD tools to compile the large design, which is now annotated with their subsystems, to obtain the final bitstream. Experiments show that the proposed strategy can lead to a performance gain of over 60% while still achieving more than 20% reduction in energy consumption.

In this paper, we develop an access controller management model which provides new opportunities for further reducing the computation repetition and data transmission redundancy for Mobile Edge Computing (MEC) in 5G network. We propose novel algorithms for solving the offloading problem with consideration of tradeoff between energy consumption and the amount of offloaded data under constraint of overall task computation time. For sequential topology applications, we develop a dynamic programming algorithm to produce optimal solutions. For general topology applications, a critical-path based heuristic algorithm is proposed by repeatedly identifying partial critical path (PCP) from the application task graph and calculating optimal solution for the PCP by performing the proposed dynamic programming algorithm. In addition, the interference of parallel data transmission between tasks (one-to-many, manyto-one and many-to-many) using single channel is taken into consideration. Experimental results demonstrate the effectiveness of our proposed method.

Recent breakthrough in wireless energy transfer technology has enabled wireless sensor networks (WSNs) to operate with zero-downtime through the use of mobile energy chargers (MCs), that periodically replenish the energy supply of the sensor nodes. Due to the limited battery capacity of the MCs, a significant number of MCs and charging depots are required to guarantee perpetual operations in large scale networks. Existing methods for reducing the number of MCs and charging depots treat the charging tour planning and depot positioning problems separately even though they are inter-dependent. This paper is the first to jointly consider charging tour planning and MC depot positioning for large-scale WSNs. The proposed method solves the problem through the following three stages: charging tour planning, candidate depot identification and reduction, and depot deployment and charging tour assignment. The proposed charging scheme also considers the association between the MC charging cycle and the operational lifetime of the sensor nodes, in order to maximize the energy efficiency of the MCs. This overcomes the limitations of existing approaches, wherein MCs with small battery capacity ends up charging sensor nodes more frequently than necessary, while MCs with large battery capacity return to the depots to replenish themselves before they have fully transferred their energy to the sensor nodes. Compared with existing approaches, the proposed method leads to an average reduction in the number of MCs by 64%, and an average increase of 19.7 times on the ratio of total charging time over total traveling time.

Data replication enhances data availability and thereby improves the system reliability and efficiency while reduces access latency and communication cost. A critical issue in data replication is to wisely place data replicas which involves identifying the best possible nodes to duplicate data according to user requests. In this paper, we address the problem of replica placement and update in tree networks, where some nodes of the network contain pre-existing replicas. It is obvious that reusing a pre-existing replica leads to smaller cost than creating a new replica, thus it is necessary to take full advantage of the pre-existing replicas. The only previous work that consider the same problem tries to find the optimal solution by developing a dynamic programming algorithm which runs in O(N5). However, this approach is not suitable for practical situation where the user requests change frequently. In this paper, we develop efficient algorithms to accelerate the replica placement without causing obvious degradation in solution quality. We first propose an efficient heuristic algorithm (named GreedyRP) for quickly placing replicas when users change their requests. Then a tabu search algorithm (named TSRP) is customized to further refine the solution obtained by algorithm GreedyRP. Experimental results show that, on tree networks with 600 nodes and 150 pre-existing replicas, the proposed algorithms can accelerate the previous work by 87.97% while the quality degradation is bounded by 2.49% in comparison to the optimal solution.

Large scale multiprocessor array suffers from frequent hardware defects or soft faults due to overheating, overload or occupancy by other running applications. To obtain fault-free logical array, reconfiguration techniques are proposed to reuse the fault-free PEs by changing the interconnection among PEs. Previous research has worked on this topic but assume that switches and links are fault-free. In this paper, we consider faults not only on the processing elements (PEs) but also on the switches and links, and develop efficient algorithms to construct as large as possible logical arrays with optimized networks length. To deal with the faults on switches and links, an efficient pre-processing procedure is designed, in which switch faults are transformed into link faults, and then faulty links are classified into several categories to handle. Then, we propose an efficient algorithm, A-MLA, to produce as many as possible logical columns which are then combined to form a two dimensional processor array. After that, we propose an algorithm A-TMLA to reduce the interconnection length of the logical array obtained by algorithm A-MLA, as short interconnect leads to small communication latency and power consumption. Extensive experimental results show that, even with switch faults and link faults, our approach can produce larger logical fault-free arrays with shorter interconnection length, compared to the state-of-the-art.

With the increased density of three-dimensional (3D) processor arrays, faults can potentially occur quite often due to power overheating during massively parallel computing. In order to achieve fault-tolerance under such a scenario, an effective way is to find an as large as possible logical fault-free subarray of m' × n' × h' from a faulty array of m × n × h (m' ≤ m, n' ≤ n, h' ≤ h), such that an original application can still work on the m' × n' × h' subarray. This paper investigates the problem of constructing maximum fault-free subarrays with minimum interconnection length from 3D arrays with faults. First, we prove that constructing maximum logical array (MLA) is NP-complete. We propose a linear-time algorithm which is capable of producing an MLA for the problem with the constraint of selected indexes. Second, we prove that minimizing the interconnection length (inter-length) of the MLA is NP-hard. We propose an efficient heuristic which significantly reduces the inter-length by revising each logical plane of the MLA. This leads to the reduction of communication cost, capacitance and dynamic power dissipation. In addition, we propose a lower bound for the inter-length of the MLA to evaluate the proposed algorithms. Simulation results show that, the size of logical array can be improved up to 62.6 percent in average, and the inter-length redundancy can be reduced by 22.7 percent in average, compared to the state-of-the-art, for all cases considered.

Reducing the interconnection length of VLSI arrays leads to less capacitance, power dissipation and dynamic communication cost between the processing elements (PEs). This paper develops efficient algorithms for constructing tightly-coupled subarrays from the mesh-connected VLSI arrays with faulty PEs. For a given size r·s of the target (logical) array, the proposed algorithm searches and reroutes a physical r×s subarray that has the least number of faults, resulting in an approximate target array, which is subsequently extended to the desired target array. Experimental results show that over 65 percent redundant interconnects can be reduced for a 64×64 target array on the 512×512 host array with no more than 1 percent faults. In addition, we propose a recursive divide-and-conquer algorithm for constructing the maximum target array (MTA). The lower bound of the total interconnection length of the MTA has been established. Experimental results show that the proposed algorithm is capable of reducing the long interconnects by over 33 percent for the MTA derived from the 512×512 host array with no more than 1 percent faults. Moreover, the proposed total interconnection length of target array is close to the lower bound for the cases with relatively fewer number of faults.

Fast reconfiguration is one of the main challenges in fault tolerant VLSI arrays. In these arrays, there are some invalid processing elements (PEs) that are fault-free but cannot be used to form a target array. These invalid PEs lead to backtracking in reconfiguration. This paper proposes a non-backtracking reconfiguration (NBR) algorithm for three-dimensional degradable VLSI array with faults. The proposed algorithm accelerates the reconfiguration without loss of harvest, by eliminating the backtracking operation that frequently occurs in the existing algorithm (named as BGPR) cited in this paper. Initially, the invalid PEs are identified in the preprocessing for the host array. Then NBR algorithm constructs each logical plane from bottom to top in the host array, and updates the set of the invalid PEs in the host array after a logical plane is constructed. Experimental results show that the NBR algorithm is more scalable than the BGPR algorithm, and thus it can reconfigure large host arrays much faster. In addition, the runtime of NBR algorithm tends to decrease, rather than increase as did in BGPR algorithm, with the increasing fault density.

Mesh-connected processor array is a popular architecture used in parallel processing. Extensive studies have been conducted on reconfiguration algorithms for the processor arrays with faults, but few work is on parallel algorithm to accelerate the reconfiguration. This paper presents a fast algorithm to reconfigure two dimensional mesh-connected processor arrays with faults. A traditional algorithm is successfully accelerated in the manner of multithread, without loss of harvest. The proposed algorithm reconfigures the processor array with the mechanics of route distance in order to avoid the routing errors. Simulation results show that the proposed algorithm can accelerate the reconfiguration nearly by 15 times on a 64 × 64 array in comparison to the traditional algorithm cited in this paper.