Human action recognition using commercial millimeter wave radar is gaining significant attention in smart elderly care and smart homes. Due to privacy concerns, the sensing data often needs to be processed locally on embedded systems with restricted computational resources, necessitating a balance between recognition accuracy and efficiency. In this paper, we propose a fast human action recognition framework based on 3D point cloud sequences generated by commercial 4D millimeter wave imaging radar systems. The framework comprises two primary phases: data preprocessing and spatial-temporal feature extraction. During the data preprocessing phase, we employ a sliding window approach for frame fusion to enhance the spatial information of the sparse point cloud while retaining its temporal features. Additionally, Morton coding is used to address the disorderliness in the point cloud sequence. For spatial-temporal feature extraction, we introduce an innovative two-stage algorithm. In the spatial feature extraction stage, we initially extract local spatial features for each point, utilizing self-attention to construct a local graph and circumvent the limitations of using Euclidean distance in sparse point clouds. Subsequently, 3D frame fusion convolution is applied to extract spatial features at the frame level, reducing the length of the spatial feature map sequence and lowering computational requirements for subsequent temporal feature extraction. In the temporal feature extraction stage, we employ a modified Transformer encoder with fine-grained feature fusion to extract temporal features. We conducted comprehensive experiments using both our collected dataset and the open dataset RadHar. The experimental outcomes demonstrate that our framework not only improves inference accuracy but also maintains satisfactory real-time performance on embedded platforms with constrained computational resources. When compared with state-of-the-art (SOTA) methods, our framework significantly enhances inference speed while retaining competitive inference accuracy. Codes and dataset are available at https://github.com/Feiyuyu0503/FastHAR.

Summary Convolutional neural networks (CNNs) have shown remarkable advantages in a wide range of domains at the expense of huge parameters and computations. Modern CNNs still tend to be more complex and larger to achieve better inference accuracy. However, the complex and large structures of CNNs could slow down the inference speed. Recently, Compressing the convolutional weights to be sparse by pruning the unimportant parameters has been demonstrated as an efficient way to reduce the computations of CNNs. On the other hand, field‐programmable gate arrays (FPGAs) have been a popular hardware platform to accelerate CNN inference. In this paper, we propose an algorithm/hardware co‐optimized method for accelerating CNN inference on FPGAs. For the algorithm, we take advantage of unstructured and structured parameter sparsifying methods to achieve high sparsity and keep the regularity of convolutional weights. Correspondingly, hardware‐friendly index representations of sparse convolutional weights are proposed. For the hardware architecture, we propose row‐wise input‐stationary dataflow, which is tightly coupled with the algorithm. A row‐wise computing engine (RConv Engine) is proposed, which is based on the dataflow. Inside the RConv Engine, the scalar‐vector structure is applied to implement the basic processing elements (PEs). To flexibly calculate the feature map with various sizes, the PEs are organized in a 2D structure with two work modes. The experimental results demonstrate that our co‐optimized method implements high sparsity of convolutional weights, and the computing engine achieves high computation efficiency. Compared with other accelerators, our co‐optimized method implements a 10.9 speedup on FPS at most with the highest sparsity of convolutional weights and negligible accuracy loss.

Graph partitioning, a preliminary step of distributed graph processing, has been attracting increasing attention in the last decade. A high quality graph partitioning algorithm should facilitate graph processing by minimizing the communication overhead and maintaining the load balancing among distributed computing units. Offline partitioning algorithms usually require the knowledge of a complete graph, and therefore, are not adaptive to handle massive graph-structured data. On the contrary, streaming partitioning algorithms take edges or vertices as a stream and make partitioning decisions on the fly. However, the streaming manner faces dilemmas from time to time because of a lack of knowledge. Furthermore, an unmindful partitioning decision in such a dilemma could significantly decrease the partition quality. In this paper, we propose a novel window-based streaming graph partitioning algorithm (WSGP). WSGP leverages a greedy-based heuristic to perform edge partitioning. When facing a decision dilemma, WSGP utilizes a size-bounded window to buffer the edges. When the window is fully filled, an edge is poped and assigned to a partition. The assignment is decided by knowledge obtained from both the edges already settled and the ones still cached in the buffer window. Our experiments take into account various real-world benchmark graphs. The experimental results demonstrate that WSGP consistently has a smaller replication factor than the state-of-the-art algorithms by up to 23%, at a limited cost in terms of memory and comprehensive running time.

Summary Energy efficiency in heterogeneous computing systems has attracted increasing interests due to its economic and environmental impacts during recent decades. Based on power‐aware hardware techniques, such as dynamic voltage frequency scaling, efforts have been made through task scheduling to reduce the total energy consumption for executing a parallel application while maintaining its time efficiency. In this case, energy conscious task scheduling refers to a bi‐objective optimization that aims to minimize the overall completion time (makespan) and the total energy consumption, simultaneously. Existing energy conscious scheduling algorithms conduct energy optimization by means of slack reclamation or a trade‐off function. However, the performance of slack reclamation has been proved to be upper‐bounded and methods relying on trade‐off functions cannot guarantee bi‐objective optimization. In this article, an energy conscious task scheduling algorithm is proposed to tackle the above issues based on the framework of variable neighborhood search. Two neighborhood structures are designed to reduce makespan and the total energy consumption, respectively. Furthermore, a pruning technique is incorporated into the algorithm to accelerate the searching process. Extensive experimental results on both randomly generated and real‐world applications demonstrate that the proposed algorithm improves the time‐efficient schedules on average by 22.4% for the energy consumption and 1.2% for the makespan.

Link prediction, which centers on whether or not a pair of nodes is likely to be connected, is a fundamental problem in complex network analysis. Network-embedding-based link prediction has shown strong performance and robustness in previous studies on complex networks, recommendation systems, and knowledge graphs. This approach has certain drawbacks, however; namely, the hierarchical structure of a subgraph is ignored and the importance of different nodes is not distinguished. In this study, we established the Subgraph Hierarchy Feature Fusion (SHFF) model for link prediction. To probe the existence of links between node pairs, the SHFF first extracts a subgraph around the two nodes and learns a function to map the subgraph to a vector for subsequent classification. This reveals any link between the two target nodes. The SHFF learns a function to obtain a representation of the extracted subgraph by hierarchically aggregating the features of nodes in that subgraph, which is accomplished by grouping nodes with similar structures and assigning different importance to the nodes during the feature fusion process. We compared the proposed model against other state-of-the-art link-prediction methods on a wide range of data sets to find that it consistently outperforms them.

We study an online fault-tolerant bin packing problem that models reliable resource allocation. In this problem, each item is replicated and has f + 1 replicas including one primary and f standbys. The packing of items is required to tolerate up to f faulty bins, i.e., to guarantee that at least one correct replica of each item is available regardless of which f bins turn to be faulty. Any feasible packing algorithm must satisfy an exclusion constraint and a space constraint. The exclusion constraint is generalized from the fault tolerance requirement and the space constraint comes from the capacity planning. The target of bin packing is to minimize the number of bins used. We first derive a lower bound on the number of bins needed by any feasible packing algorithm. We then study three heuristic algorithms named mirroring, shifting and mixing under a particular setting where all items have the same size. The mirroring algorithm has a low utilization of the bin capacity. Compared with the mirroring algorithm, the shifting algorithm requires fewer bins. However, in online packing, the process of opening bins by the shifting algorithm is not smooth. It turns out that even for packing a few items, the shifting algorithm needs to quickly open a large number of bins. The mixing algorithm adopts a dual average strategy to gradually open new bins for incoming items. We prove that the mixing algorithm is feasible and show that it balances the number of bins used and the process of opening bins. Finally, to pack items with different sizes, we extend the mirroring algorithm by adopting the First-Fit strategy and extend both the shifting and mixing algorithms by involving the harmonic strategy. The asymptotic competitive ratios of the three extended algorithms are analyzed respectively.

We study an interval job scheduling problem in distributed systems. We are given a set of interval jobs, with each job specified by a size, an arrival time and a processing length. Once a job arrives, it must be placed on a machine immediately and run for a period of its processing length without interruption. The homogeneous machines to run jobs have the same capacity limits such that at anytime, the total size of the jobs running on any machine cannot exceed its capacity. Launching each machine incurs a fixed cost. After launch, a machine is charged a constant cost per time unit until it is terminated. The problem targets to minimize the total cost incurred by the machines for processing the given set of interval jobs. We focus on the algorithmic aspects of the problem in this article. For the special case where all the jobs have a unit size equal to the machine capacity, we propose an optimal offline algorithm and an optimal 2-competitive online algorithm. For the general case where jobs can have arbitrary sizes, we establish a non-trivial lower bound on the optimal solution. Based on this lower bound, we propose a 5-approximation algorithm in the offline setting. In the non-clairvoyant online setting, we design a O(μ)-competitive Modified First-Fit algorithm which is near optimal (μ is the max/min job processing length ratio). In the clairvoyant online setting, we propose an asymptotically optimal O(√log μ)-competitive algorithm based on our Modified First-Fit strategy.

In modern data intensive computing, it is increasingly common for jobs to be executed in a distributed fashion across multiple machine clusters or datacenters to take advantage of data locality. This paper studies fair resource allocation among jobs requiring distributed execution. We extend conventional max-min fairness for resource allocation in a single machine or machine cluster to distributed job execution over multiple sites and define Aggregate Max-min Fairness (AMF) which requires the aggregate resource allocation across all sites to be max-min fair. We show that AMF satisfies the properties of Pareto efficiency, envy-freeness and strategy-proofness, but it does not necessarily satisfy the sharing incentive property. We propose an enhanced version of AMF to guarantee the sharing incentive property. We present algorithms to compute AMF allocations and propose an add-on to optimize the job completion times under AMF. Experimental results show that compared with a baseline which simply requires the resource allocation at each site to be max-min fair, AMF performs significantly better in balancing resource allocation and in job completion time, particularly when the workload distribution of jobs among sites is highly skewed.

We consider an online fault-tolerant bin packing problem that models the reliable resource allocation in cloud-based systems. In this problem, any feasible packing algorithm must satisfy an exclusion constraint and a space constraint. The exclusion constraint is generalized from the fault-tolerance requirement and the space constraint comes from the capacity planning. The target of bin packing is to minimize the number of bins used. We first derive a lower bound on the number of bins needed by any feasible packing algorithm. Then we study two heuristic algorithms mirroring and shifting. The mirroring algorithm has a low utilization of the bin capacity. Compared with the mirroring algorithm, the shifting algorithm requires fewer numbers of bins. However, in online packing, the process of opening bins by the shifting algorithm is not smooth. It turns out that even for packing a few items, the shifting algorithm needs to quickly open a large number of bins. We therefore propose a new heuristic algorithm named mixing which can gradually open new bins for incoming items. We prove that the mixing algorithm is feasible and show that it balances the number of bins used and the process of opening bins.

We consider the approximate consensus problem in a partially connected network of n nodes where at most f nodes may suffer from Byzantine faults. We study under which conditions this problem can be solved using an iterative algorithm. A Byzantine node can equivocate: it may provide different values to its neighbors. To restrict the possibilities of equivocation, the 3-partial multicast primitive is considered. When a (correct or faulty) node uses this communication primitive, it provides necessarily the same value to the two identified receivers. Based on this communication primitive, a novel condition called f-resilient is proposed and proved to be necessary and sufficient to solve the approximate Byzantine consensus problem in a synchronous network. This condition takes into account two different communication primitives: unicast and 3-partial multicast. It expresses a trade-off between the two known approaches that make the problem solvable (increasing the number of neighbors or/and increasing the power of the communication primitives). The condition f-resilient does not require to eliminate all the possibilities of equivocation. Furthermore, it can be satisfied when there is just a majority of correct nodes. The relationships between the condition f-resilient and the condition h-disjoint (proposed by Alexander Jaffe et al. in 2012 to solve another problem, namely exact Byzantine consensus) are investigated. Two preliminary conclusions are obtained. When a network does not satisfy h-disjoint, it also does not satisfy f-resilient. But when a network satisfies h-disjoint, f-resilient is not necessarily satisfied. Finally, the condition is extended to cope with asynchronous networks.

We consider the clock synchronization problem in wireless mobile ad hoc networks in the presence of Byzantine nodes. The communication topology is dynamic: nodes move randomly within a geographical area. We propose a clock synchronization protocol which is based on the linear approximate consensus method. Periodically each correct node broadcasts its current timestamp and gathers the timestamps provided by its current neighbors. To cope with the malicious nodes (and to improve the performance when the node density is low), each node keeps the collected timestamps in a local log. As a log may contain values received more or less recently, a transformation technique is introduced to refresh the outdated values. The accuracy of the synchronisation depends on the connectivity among the moving nodes. We use a matrix and vector based representation to model the behavior of the synchronization process and to analyze its accuracy. We show that the deviation between the different clock values can converge towards zero when a particular condition is satisfied infinitely often. The frequency at which the condition is satisfied also impacts the synchronization accuracy. Based on a particular mobility scenario, performance simulations are conducted.