BACKGROUND: Quantitatively tracking subcellular protein puncta over time is critical for understanding protein functions and related cellular processes, as many proteins assemble into discrete protein puncta when performing functions. Monitoring these protein puncta over an extended period enables the quantitation of their dynamic behaviors, such as repositioning, remodeling, and inter-object interactions such as fusion and split. These characteristics are essential for deciphering the underlying regulatory mechanisms of protein function. However, tracking protein puncta is challenging due to these clusters undergoing rapid and complex temporal changes. RESULTS: To address these challenges, a comprehensive tool ‘ProTrack3D’ is developed. It implements a multi-stage multi-object tracking workflow specifically designed to handle the complexity of dynamic protein puncta. The segmentation stage can adopt any advanced deep neural network to detect protein puncta. The Tracking stage follows individual puncta over time and detects birth, death, split and fusion events. The Life Path Reconstruction stage visualizes the life history of protein puncta using tree structures. Applying ProTrack3D tool to the 4D fluorescence microscopy images of developing Drosophila embryos confirms the effectiveness of the method implemented at each stage. Compared with existing tracking tools, our tracking algorithm achieves significant improvement in tracking performance by utilizing deep feature maps which encode rich spatial and intensity information. CONCLUSIONS: By integrating all stages of tracking and offering quantitative analysis functions with a user-friendly graphical interface, ProTrack3D enables researchers with basic computer skills to perform segmentation, tracking, and analysis of protein puncta in fluorescence microscopy images, thus facilitating the broader accessibility and usability of advanced protein tracking techniques. ProTrack3D is available for distribution via GitHub at https://github.com/ramugautam1/ProTrack3D .

Multi-chiplet system design, by integrating multiple chiplets/dielets within a single package, has emerged as a promising paradigm in the post-Moore era. This paper introduces a novel task mapping algorithm for multi-chiplet based many-core systems, addressing the unique challenges posed by intra- and inter-chiplet communications under power and thermal constraints. Traditional task mapping algorithms fail to account for the latency and bandwidth differences between these communications, leading to sub-optimal performance in multi-chiplet systems. Our proposed algorithm employs a two-step process: (1) task assignment to chiplets using binary linear programming, leveraging a totally unimodular constraint matrix, and (2) intra-chiplet mapping that minimizes communication latency while considering both thermal and power constraints. This method strategically positions tasks with extensive inter-chiplet communication near interface nodes and centralizes those with predominant intra-chiplet communication. Experimental results demonstrate that the proposed algorithm outperforms existing methods (DAR and IOA) with a 37.5% and 24.7% reduction in execution time, respectively. Communication latency is also reduced by up to 43.2% and 32.9%, compared to DAR and IOA. These findings affirm that the proposed task mapping algorithm aligns well with the characteristics of multi-chiplet based many-core systems, and thus improves optimal performance.

Inter- and intra-chiplet interconnection networks play a vital role in the operation of many core systems made of multiple chiplets. However, these networks are susceptible to faults caused by manufacturing defects and attacks resulting from the malicious insertion of hardware Trojans and backdoors. Unlike conventional fault-tolerant or countermeasure methods, this article focuses on optimizing network robustness to withstand both faults and attacks, while considering the constraints of chiplet area and power budget. To achieve this, this article first defines network robustness as a quantifiable measure based on various network parameters, after which an optimization problem is formulated to optimize the robustness of the network topology. To efficiently solve this problem, a reinforcement learning algorithm is proposed. Experimental results demonstrate that the proposed method is capable of generating inter- and intra-chiplet interconnection networks that are significantly more robust than existing topology generation methods. Specifically, the proposed method improves robustness over ButterDonut and Kite, respectively, by an average of 10.88% and 14.06% under random faults and by 9.37% and 7.81% under targeted attacks. These experimental results confirm that the proposed method is capable of generating robust inter- and intra-chiplet interconnection networks that can withstand both faults and attacks. By optimizing the network topology’s robustness, it provides a valuable contribution to the design and security of chiplet-based core systems.

Fully Homomorphic Encryption (FHE) is regarded as a promising way to protect data privacy with encrypted computation. Due to high computation overhead, hardware based FHE accelerators were proposed to speed up FHE applications. To support complicated FHE-encrypted neural network applications, multi-chiplet based FHE accelerators were further proposed for scaling up system size, whereas one of the challenges is designing efficient intra- and inter-chiplet interconnection networks to accelerate data transfer. Conventional regular topologies like mesh or Kite either lead to high inter-chiplet transmission latency or excessive power consumption as these topologies assume uniform bandwidth or radix for nodes/links, ignoring the highly irregular distribution of inter-chiplet communication volumes. On the other hand, the problem of generating customized intra- and inter-chiplet interconnection networks has high complexity and previous network-on-chip topology generation works cannot efficiently improve the performance of intra- and inter-chiplet interconnection networks. In this article, the intra- and inter-chiplet interconnection optimization problem is defined, aiming to minimize the execution time of FHE applications under cost and power constraints. To efficiently solve this problem, we propose a bilevel optimization algorithm, which decomposes the problem into three sub-problems: (1) FHE parameters selection, (2) task-to-core mapping, and (3) intra-/inter-chiplet interconnection network topology generation. These sub-problems are then solved iteratively. Experimental results demonstrate that our proposed method reduces execution time by 51.66%, 43.16%, 39.44%, 43.34%, and 27.70% compared with REED and four multi-chiplet based FHE accelerators with mesh, Kite, Butterfly, and Florets as inter-chiplet interconnection networks. Therefore, the proposed method can effectively accelerate FHE applications on large-scale multi-chiplet systems.

MOTIVATION: While multi-channel fluorescence microscopy is a vital imaging method in biological studies, the number of channels that can be imaged simultaneously is limited by technical and hardware limitations such as emission spectra cross-talk. One solution is using deep neural networks to model the localization relationship between two proteins so that the localization of one protein can be digitally predicted. Furthermore, the input and predicted localization implicitly reflect the modeled relationship. Accordingly, observing the response of the prediction via manipulating input localization could provide an informative way to analyze the modeled relationships between the input and the predicted proteins. RESULTS: We propose a protein localization prediction (PLP) method using a cGAN named 4D Reslicing Generative Adversarial Network (4DR-GAN) to digitally generate additional channels. 4DR-GAN models the joint probability distribution of input and output proteins by simultaneously incorporating the protein localization signals in four dimensions including space and time. Because protein localization often correlates with protein activation state, based on accurate PLP, we further propose two novel tools: digital activation (DA) and digital inactivation (DI) to digitally activate and inactivate a protein, in order to observing the response of the predicted protein localization. Compared with genetic approaches, these tools allow precise spatial and temporal control. A comprehensive experiment on six pairs of proteins shows that 4DR-GAN achieves higher-quality PLP than Pix2Pix, and the DA and DI responses are consistent with the known protein functions. The proposed PLP method helps simultaneously visualize additional proteins, and the developed DA and DI tools provide guidance to study localization-based protein functions. AVAILABILITY AND IMPLEMENTATION: The open-source code is available at https://github.com/YangJiaoUSA/4DR-GAN. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In response to growing security challenges facing many-core systems imposed by thermal covert channel (TCC) attacks, a number of threshold-based detection methods have been proposed. In this paper, we show that these threshold-based detection methods are inadequate to detect TCCs that harness advanced signaling and specific modulation techniques. Since the frequency representation of a TCC signal is found to have multiple side lobes, this important feature shall be explored to enhance the TCC detection capability. To this end, we present a pattern-classification-based TCC detection method using an artificial neural network that is trained with a large volume of spectrum traces of TCC signals. After proper training, this classifier is applied at runtime to infer TCCs, should they exist. The proposed detection method is able to achieve a detection accuracy of 99%, even in the presence of the stealthiest TCCs ever discovered. Because of its low runtime overhead ($< 0.187\%$) and low energy overhead ($< 0.072\%$), this proposed detection method can be indispensable in fighting against TCC attacks in many-core systems. With such a high accuracy in detecting TCCs, powerful countermeasures, like the ones based on dynamic voltage and frequency scaling (DVFS), can be rightfully applied to neutralize any malicious core participating in a TCC attack.

In a many-core chip, thermal flux and thermal correlation among the cores can be explored to create a thermal covert channel (TCC). In this paper, we provide an analytical model to quickly determine the key TCC performance metrics, in terms of bit error rate (BER), signal to noise ratio (SNR), and channel capacity, without going through lengthy computer simulation and/or physical experiments that are normally needed in current TCC performance studies. According to our model, the TCC’s BER is proportional to the square root of the transmission frequency, which can be explored quantitatively to boost the TCC’s transmission efficiency by letting the TCC’s thermal signal be transmitted at a higher frequency. In addition, our proposed model also links the jamming noise and application of Dynamic Voltage Frequency Scaling (DVFS) to TCC’s BER performance, a feature that can be explored to design/optimize the countermeasures against the TCC attacks. The TCC performance predicted by the proposed theoretical model is found in a good agreement with that obtained from computer simulations, with an average error lower than 7%.

The in-vivo functions of many proteins highly depend on their ability to assemble into supramolecular complexes at specific subcellular localizations. Such subcellular localizations can change in response to intracellular and extracellular cues, which is an important way to regulate the behavior and morphology of the cell. Therefore, segmentation and tracking of these supramolecular complexes are critical in understanding gene functions and regulations. Proteins that form discrete puncta or clusters can be tracked for a long period of time. However, segmentation and tracking become challenging when protein complexes undergo quick repositioning and remodeling such as assembly, disassembly, fusion, and split. In this paper, we first use deep learning methods to segment and track protein clusters with changing morphology, size, and intensity in hyperdimensional biological images. Using the segmentation and tracking results, we reconstruct the life paths and family tree of the protein clusters by integrating fusion and split events. Based on the family trees, various quantitative analyses can be performed including temporal correlations between the tracked protein and its interacting protein complexes. The effectiveness of the proposed method for analyzing subcellular proteins is confirmed through the evaluation using the two-channel 3D fluorescent microscopy time-lapse videos (5D images) of developing Drosophila embryos.

Thermal covert channel (TCC) attacks have been a serious security concern to the use of many-core chips. Severity of these attacks is directly linked to the TCC’s transmission rate and its BER (bit error rate) performance, both of which are impacted by the transmission characteristics of thermal signals and adopted encoding, modulation, and multiplexing schemes. This paper examines, compares, and analyzes various TCCs built upon different combinations of encoding, modulation, and multiplexing. In particular, our study shows that TCC using non-return-to-zero (NRZ) line coding and frequency shift keying (FSK) modulation achieves the highest throughput of 120 bps and BER of below 10%.

As an effective scheme often adopted for performance tuning in many-core processors, task migration provides an opportunity for “hot” tasks to be migrated to run on a “cool” core that has a lower temperature. When a task needs to migrate from one processor core to another, the migration can embark on numerous modes defined by the migration paths undertaken and/or the destinations of the migration. Selecting the right migration mode that a task shall follow has always been difficult, and it can be more challenging with the existence of dark cores that can be called back to service (reactivated), which ushers in additional task migration modes. Previous works have demonstrated that dark cores can be placed near the active cores to reduce power density so that the active cores can run at higher voltage/frequency levels for higher performance. However, the existing task migration schemes neither consider the impact of dark cores on each application's performance, nor exploit performance trade-off under different migration modes. Unlike the existing task migration schemes, in this article, a runtime task migration algorithm that simultaneously takes both migration modes and dark cores into consideration is proposed, and it essentially has two major steps. In the first step, for a specific migration mode that is tied to an application whose tasks need to be migrated, the number of dark cores is determined so that the overall performance is maximized. The second step is to find an appropriate core region and its location for each application to optimize the communication latency and computation performance; during this step, focus is placed on reducing the fragmentation of the free core regions resulting from the task migration. Experimental results have confirmed that our approach achieves over 50 percent reduction in total response time when compared to recently proposed thermal-aware runtime task migration approachess.

The thermal covert channels (TCCs) in many-core systems can cause detrimental data breaches. In this article, we present a three-step scheme to detect and fight against such TCC attacks. Specifically, in the detection step, each core calculates the spectrum of its own CPU workload traces that are collected over a few fixed time intervals, and then it applies a frequency scanning method to detect if there exists any TCC attack. In the next positioning step, the logical cores running the transmitter threads are located. In the last step, the physical CPU cores suspiciously engaging in a TCC attack have to undertake dynamic voltage frequency scaling (DVFS) such that any possible TCC trace will be essentially wiped out. Our experiments have confirmed that on average 97% of the TCC attacks can be detected, and with the proposed defense, the packet error rate (PER) of a TCC attack can soar to more than 70%, literally shutting down the attack in practical terms. The performance penalty caused by the inclusion of the proposed DVFS countermeasures is found to be only 3% for an$8\times 8$many-core system.

Many-core systems are susceptible to attacks launched by thermal covert channel (TCC) attacks. Detection of TCC attacks often relies on the use of threshold-based approaches or variants, and a countermeasure to thwart the channel can be applied only after an attack is deemed to be present. In this article, we describe a direct sequence spread spectrum (DSSS)-based TCC, where its thermal data are modulated by a pseudo-random bit sequence. Unfortunately, such DSSS-based TCC has an extremely low signal strength that the signal is nearly indistinguishable from the noise and thus cannot be detected by any existing threshold-based detection methods. To combat this stealthy TCC, we propose a novel detection scheme that lets the received signal pass through a differential filter where irrelevant frequency components occupied mainly by the noise gets eliminated and the filtered signal is next compared against a threshold for successful detection. Experimental results show that the DSSS-based TCC can effectively survive detection by the existing detection methods with its BER as low as 4%. In contrast, with the proposed detection and countermeasure applied, the detection accuracy jumps to 89%, and the BER of the DSSS-based TCC soars to 50%, which indicates that the TCC is practically shut down.

As the network-on-chip (NoC) integrated into an SoC design can come from an untrusted third party, there is a growing risk that data integrity and security get compromised when supposedly sensitive data flows through such an untrusted NoC. We thus introduce a new method that can ensure secure and secret data transmission over such an untrusted NoC. Essentially, the proposed scheme relies on encoding binary data as delays between packets travelling across the source and destination pair. The maximum data transmission rate of this inter-packet-delay (IPD)-based communication channel can be determined from the analytical model developed in this article. To further improve the undetectability and robustness of the proposed data transmission scheme, a new block coding method and communication protocol are also proposed. Experimental results show that the proposed IPD-based method can achieve a packet error rate (PER) of as low as 0.3% and an effective throughput of$\boldsymbol {2.3\times 10^{5}}$b/s, outperforming the methods of thermal covert channel, cache covert channel, and circuit-based encryption and, thus, is suitable for secure data transmission in unsecure systems.

Although it has been demonstrated in multiple studies that serious data leaks could occur to many-core systems thanks to the existence of the thermal covert channels (TCC), little has been done to produce effective countermeasures that are necessary to fight against such TCC attacks. In this paper, we propose a three-step countermeasure to address this critical defense issue. Specifically, the countermeasure includes detection based on signal frequency scanning, positioning affected cores, and blocking based on Dynamic Voltage Frequency Scaling (DVFS) technique. Our experiments have confirmed that on average 98% of the TCC attacks can be detected, and with the proposed defense, the bit error rate of a TCC attack can soar to 92%, literally shutting down the attack in practical terms. The performance penalty caused by the inclusion of the proposed countermeasures is only 3% for an 8×8 system.

Networks-on-chips (NoCs) have become the mainstream communication infrastructure for chip multiprocessors (CMPs) and many-core systems. The commonly used parallel applications and emerging machine learning-based applications involve a significant amount of collective communication patterns. In CMP applications, multicast is widely used in multithreaded programs and protocols for barrier/clock synchronization and cache coherence. Multicast routing plays an important role on the system performance of a CMP. Existing partition-based multicast routing algorithms all use static destination set partition strategy which lacks the global view of path optimization. In this paper, we propose an efficient Dynamic Partition Merging (DPM)-based multicast routing algorithm. The proposed algorithm divides the multicast destination set into partitions dynamically by comparing the routing cost of different partition merging options and selecting the merged partitions with lower cost. The simulation results of synthetic traffic and PARSEC benchmark applications confirm that the proposed algorithm outperforms the existing path-based routing algorithms. The proposed algorithm is able to improve up to 23% in average packet latency and 14% in power consumption against the existing multipath routing algorithm when tested in PARSEC benchmark workloads.

As a means to thwart thermal covert channel attack in a multi-/many-core system, a strong heat noise whose frequency band coincides with that occupied by the thermal covert channel is injected to jam the channel. However, this undiscriminating channel jamming-based countermeasure will fail if a thermal covert channel is allowed to change its transmission frequency dynamically in response to the jamming. To combat this enhanced thermal covert channel, a more advanced countermeasure is needed and thus proposed that checks the frequency spectrum and tracks any possible covert channel. Only after a channel is detected to be susceptible, a thermal noise with this channel frequency is then emitted to jam the covert channel. The communication protocols and frequency changing scheme pertaining to this enhanced thermal covert channel are described in this article. The experimental results confirm that, when the proposed countermeasure is applied, the enhanced thermal covert channel, much more resilient to jamming, suffers from an extremely high packet error rate (PER), which makes any meaningful data leakage practically impossible. As the proposed countermeasure method is poised to contain dangerous thermal covert channel attacks with an anti-jamming capability, it lends itself well to secure multi-/many-core systems.

A number of critical design decisions, such as network topology, buffer sizes, flow control mechanism and so on so forth, have to be evaluated in any NoC the design. Designs and verifications of NoCs are based on either software simulations, which are extremely slow and inaccurate for complex models, or hardware emulations using low/mid-class FPGAs, where the scalability of the NoC system is intensively restricted by the limited on-chip resources. In this paper, we implement a parameterized NoC emulation system, capable of verifying complete functionality of routers and monitoring network performance and buffer usages in real time, on a hardware platform featuring a super large FPGA chip, Xilinx Virtex-7. This FPGA-based emulator also shall be configured to support multiple routing algorithms and packet transferring mechanisms. Compared to the existing emulators, it requires less user effort to measure the performance under various application scenarios, and it scales well to emulate large NoC designs. Currently, this emulator has been used to study NoCs with sizes of 4x4 and 8x8. For the case of 4x4 (8X8) NoC emulator, data transfers between routers can run at over 50MHz, and only occupies about 6% (25%) of the FPGA logic block resources.

In spite of escalating thermal challenges imposed by high power consumption, most reported 3D Network-on-chip (NoC) systems that adopt classic 3D cube (mesh) topology are unable to tackle the thermal management issues directly at the architectural level. Rather, to avoid chip being overheated, tasks running in a “hot” node have to be migrated to a “cooler” one, resulting in increased distance between communicating nodes and ultimately poor performance. In this paper, we propose a new 3D NoC architecture that genuinely supports runtime thermal-aware task management. Dubbed Hierarchical Ring Cluster (HRC), this new hierarchical 3D NoC architecture has three levels across its entire network hierarchy: 1) nodes are grouped as rings, 2) rings are then grouped into cubes, and 3) multiple cubes are connected to form the whole network. Routing in a HRC system is also performed in a hierarchical manner: Paths are set up within rings using low latency circuit switching, and data that need to cross the rings or cubes are routed following dimension-order routing supported by wormhole switching. In this organization, “hot” tasks that need to migrate can move along the rings without incurring increased communication distances. Our experimental results have confirmed that the proposed HRC architecture has a much lower network latency than other known 3D NoC architectures. When working with runtime thermal-aware task migration approaches, HRC can help reduce latency by as much as 80 percent compared to thermal-aware task migration approaches applied to 3D mesh NoC topologies.

Power budgeting is an essential aspect of networks-on-chip (NoC) to meet the power constraint for on-chip communications while assuring the best possible overall system performance. For simplicity and ease of implementation, existing NoC power budgeting schemes treat all the individual routers uniformly when allocating power to them. However, such homogeneous power budgeting schemes ignore the fact that the workloads of different NoC routers may vary significantly, and thus may provide excess power to routers with low workloads, whereas insufficient power to those with high workloads. In this paper, we formulate the NoC power budgeting problem in order to optimize the network performance over a power budget through per-router frequency scaling. We take into account of heterogeneous workloads across different routers as imposed by variations in traffic. Correspondingly, we propose a fine-grained solution using an agile algorithm with low time complexity. Frequency of each router is set individually according to its contribution to the average network latency while meeting the power budget. Experimental results have confirmed that with fairly low runtime and hardware overhead, the proposed scheme can help save up to$50$percent application execution time when compared with the latest proposed methods.

Power budgeting for NoC needs to be performed to meet limited power budget while assuring the best possible overall system performance. For simplicity and ease of implementation, existing NoC power budgeting schemes, irrespective of the fact that the packet arrival rates of different NoC routers may vary significantly, treat all the individual routers indiscriminately when allocating power to them. However, such homogeneous power allocation may provide excess power to routers with low packet arrival rates whereas insufficient power to those with high arrival rates. In this paper, we formulate the NoC power budgeting problem as to optimize the network performance over a power budget through per-router frequency scaling, taking into account of heterogeneous packet arrival rates across different routers as imposed by run time traffic dynamics. Correspondingly, we propose a fine-grained solution using an agile dynamic programming network with a linear time complexity. In essence, frequency of a router is set individually according to its contribution to the average network latency while meeting the power budget. Experimental results have confirmed that with fairly low runtime and hardware overhead, the proposed scheme can help save up to 50% application execution time when compared with the best existing methods.

As low-power electronics and miniaturization conspire to populate the world with emerging devices, one appealing approach is to power these multi-core/many-core-based devices with energy harvested from various environments. Of the most important issues concerning these devices is how to effectively allocate power budget among the cores competing for power, which is formulated as one specific type of power-performance optimization problem in this paper. We attempt to solve this problem by proposing an Adaptive Power Allocation Technique (APAT) that uses a dynamic programming network. Our goal here is to maximize the overall system performance, taking into account a unique yet challenging fact that, available power budget might have to undergo a significant change when a renewable energy source is scavenging. APAT has a linear time complexity and low hardware overhead. Experiments have confirmed that APAT can reduce 20 ~ 30% of execution time compared to other state-of-the-art power allocation algorithms. In addition, as APAT is quite insensitive to the changing rate of the power, lending itself well for power management in many-core systems powered by energy-harvesting sources.

Scaling of future many-core chips is hindered by the challenge imposed by ever-escalating power consumption. At its worst, an increasing fraction of the chips will have to be shut down, as power supply is inadequate to simultaneously switch all the transistors. This so-called dark silicon problem brings up a critical issue regarding how to achieve the maximum performance within a given limited power budget. This issue is further complicated by two facts. First, high variation in power budget calls for wide range power control capability, whereas most current frequency/voltage scaling techniques cannot effectively adjust power over such a wide range. Second, as the applications' behavior becomes more complicated, there is a pressing need for scalability and global coordination, rendering heuristic-based centralized or fully distributed control schemes inefficient. To address the aforementioned problems, in this paper, a power allocation method employing multiagent auction models is proposed, referred as Hierarchal MultiAgent based Power allocation (HiMAP). Tiles act the role of consumers to bid for power budget and the whole process is modeled by a combinatorial auction, whereas HiMAP finds the Walrasian equilibria. Experimental results have confirmed that HiMAP can reduce the execution time by as much as 45% compared to three competing methods. The runtime overhead and cost of HiMAP are also small, which makes it suitable for adaptive power allocation in many-core systems.

Modern network-on-chip (NoC) systems are required to handle complex runtime traffic patterns and unprecedented applications. Data traffics of these applications are difficult to fully comprehend at design time so as to optimize the network design. However, it has been discovered that the majority of dataflows in a network are dominated by less than 10% of the specific pathways. In this article, we introduce a method that is capable of identifying critical pathways in a network at runtime and can then dynamically reconfigure the network to optimize for network performance subject to the identified dominated flows. An online learning and analysis scheme is employed to quickly discover the emerging dominated traffic flows and provides a statistical traffic prediction using regression analysis. The architecture of a self-tuning network is also discussed which can be reconfigured by setting up the identified point-to-point paths for the dominance dataflows in large traffic volumes. The merits of this new approach are experimentally demonstrated using comprehensive NoC simulations. Compared to the conventional network architectures over a range of realistic applications, the proposed self-tuning network approach can effectively reduce the latency and power consumption by as much as 25% and 24%, respectively. We also evaluated the configuration time and additional hardware cost. This new approach demonstrates the capability of an adaptive NoC to handle more complex and dynamic applications.

Modern networks-on-chip (NoC) systems are required to handle complex run-time traffic patterns and unprecedented applications. Data traffics of these applications are difficult to be fully comprehended at design-time so as to optimize the network design. However, it has been discovered that the majority data flows in a network are dominated by less than 10% of the specific pathways. In this paper, we introduce a method that is capable of identifying critical pathways in a network at run-time and, then, can dynamically reconfigure the network to optimize for the network performance subjected to the identified dominated flows. An online learning and analysis scheme is employed to quickly discover the emerged dominated traffic flows and provides a statistical traffic prediction using regression analysis. The architecture of a self-tuning network is also discussed which can be reconfigured by setting up the identified point-to-point paths for the dominance data flows in large traffic volumes. The merits of this new approach are experimentally demonstrated using comprehensive NoC simulators. Compared to the conventional network architectures over a range of realistic applications, the proposed self-tuning network approach can effectively reduce the latency and power consumption by as much as 25% and 24%, respectively. We also evaluated the configuration time and additional hardware cost. This new approach demonstrates the capability of an adaptive NoC to handle more complex and dynamic applications.

In this paper, two topology oriented multicast routing algorithms, MXYZ and AL+XYZ, are proposed to support multicasting in 3D Networks on Chips (NoCs). In specific, MXYZ is a dimension order multicast routing algorithm that targets 3D NoC systems built upon regular topologies, while AL+XYZ is applicable to NoCs with irregular topologies. If the output channel found by MXYZ is not available (i.e. in the same region), an alternative output channel is used to forward/replicate the packets in AL+XYZ. MXYZ is evaluated against a path based regular topology oriented multicast routing and AL+XYZ against an irregular region oriented multiple unicast routing algorithm. Our experimental results have demonstrated that the proposed MXYZ and AL+XYZ schemes have lower latency and energy consumption than the conventional path based multicast routing and the multiple unicast routing algorithms, meriting them to be more suitable for supporting multicasting in 3D NoC systems.

Although adaptive routing algorithms promise higher communication performance, as compared to deterministic routing algorithms, they suffer from the out-of-order packet delivery problem. In the context of Network on Chip, the area and computational overhead of ordering packets at the destination is high and may reverse any gain achieved through the use of adaptivity of the routing algorithm. In this paper, we describe a novel scheme for ensuring in-order packet delivery while retaining the performance advantages of adaptive routing. The hardware architecture of a router that supports the proposed scheme is described. Although the basic idea in our proposal is topology independent we evaluate and compare the performance of our scheme with both deterministic as well as adaptive routing algorithms for 2D mesh NoC. As compared to the XY routing algorithm, our technique significantly reduces the packet delay and improves the saturation point. The impact on router area and power dissipation is also discussed. Although the power consumption of routers increase, the energy consumption per flit increases less than 2% on average, since the higher performance allows for draining more traffic during a certain time window.

In this article, we investigate the Intellectual Property (IP) mapping problem that maps a given set of IP cores onto the tiles of a mesh-based Network-on-Chip (NoC) architecture such that the power consumption due to intercore communications is minimized. This IP mapping problem is considered under both bandwidth and latency constraints as imposed by the applications and the on-chip network infrastructure. By examining various applications' communication characteristics extracted from their respective communication trace graphs, two distinguishable connectivity templates are realized: the graphs with tightly coupled vertices and those with distributed vertices. These two templates are formally defined in this article, and different mapping heuristics are subsequently developed to map them. In general, tightly coupled vertices are mapped onto tiles that are physically close to each other while the distributed vertices are mapped following a graph partition scheme. Experimental results on both random and multimedia benchmarks have confirmed that the proposed template-based mapping algorithm achieves an average of 15% power savings as compared with MOCA, a fast greedy-based mapping algorithm. Compared with a branch-and-bound--based mapping algorithm, which produces near optimal results but incurs an extremely high computation cost, the proposed algorithm, due to its polynomial runtime complexity, can generate the results of almost the same quality with much less CPU time. As the on-chip network size increases, the superiority of the proposed algorithm becomes more evident.

In communication networks, multiple disjoint communication paths are desirable for many applications. Such paths, however, may not exist in a network. In such a situation, paths with minimum link and/or node sharing may be considered. This paper addresses the following two related fundamental questions. First, in case of no solution of disjoint multiple paths for a given application instance, what are the criteria for finding the best solution in which paths share nodes and/or links? Second, if we know the criteria, how do we find the best solution? We propose a general framework for the answers to these two questions. This framework can be configured in a way that is suitable for a given application instance. We introduce the notion of link shareability and node shareability and consider the problem of finding minimum-cost multiple paths subject to minimum shareabilities (MCMPMS problem). We identify 65 different link/node shareability constraints, each leading to a specific version of the MCMPMS problem. In a previously published technical report, we prove that all the 65 versions are mutually inequivalent. In this paper, we show that all these versions can be solved using a unified algorithmic approach that consists of two algorithm schemes, each of which can be used to generate polynomial-time algorithms for a set of versions of MCMPMS. We also discuss some extensions where our modeling framework and algorithm schemes are applicable.

The overlapping layers (OL) scheme proposed in our previous work provides a solution to balance the load of cluster heads at different layers in the PMRC-based wireless sensor networks. However, in the OL scheme, the layer boundary and the overlap range are static through the network lifetime. The network lifetime is still limited by some nodes which have only one candidate cluster head. To overcome this limitation, in this paper, we propose the Minimum overlapping layers (MOL) scheme with gradually changed layer boundary through network lifetime and its variant, the MOL with initial overlap (MOLIO) scheme. The simulation results of the OL, MOL, and MOLIO schemes show that the MOL scheme significantly prolongs the network lifetime than the OL scheme for most transmission ranges and the MOLIO scheme achieves better results than the MOL scheme at larger transmission ranges.

Service-oriented wireless sensor network (WSN) has been recently proposed as an architecture to rapidly develop applications in WSNs. In WSNs, a query task may require a set of services and may be carried out repetitively with a given frequency during its lifetime. A service composition solution shall be provided for each execution of such a persistent query task. Due to the energy saving strategy, some sensors may be scheduled to be in sleep mode periodically. Thus, a service composition solution may not always be valid during the lifetime of a persistent query. When a query task needs to be conducted over a new service composition solution, a routing update procedure is involved which consumes energy. In this paper, we study service composition design which minimizes the number of service composition solutions during the lifetime of a persistent query. We also aim to minimize the total service composition cost when the minimum number of required service composition solutions is derived. A greedy algorithm and a dynamic programming algorithm are proposed to complete these two objectives respectively. The optimality of both algorithms provides the service composition solutions for a persistent query with minimum energy consumption.

A number of multi-channel assignment schemes have recently been proposed to improve the throughput of IEEE 802.11-based multi-hop wireless mesh networks (WMNs). In these schemes, channel coordination is done either through time synchronization across all the hosts, or through the use of a dedicated channel for the transmission of necessary control messages. Either way, excessive system overhead and/or waste of bandwidth resource become unavoidable, undermining the overall network throughput. To maximize the network throughput, we propose a synchronization-free, hybrid temporal-spatial multi-channel assignment scheme in a random heterogeneous network requiring only a single radio interface per host. In this scheme, the gateway is allowed to use all the available channels sequentially in a round-robin fashion. This temporal channel assignment approach ensures that all the neighboring hosts that communicate with the gateway directly shall have a fair access to the gateway. The channel assignment for the remaining wireless hosts is based on the geographical location and channel availability (a spatial approach) to avoid the interference within the communication region of each sender host in its transmission time period. Compared with another multi-channel scheme MMAC, extensive simulation results demonstrate that our proposed scheme can improve the network throughput substantially with the acceptable collision ratio.

Network-on-a-chip (NoC) is an effective approach to connect and manage the communication between the variety of design elements and intellectual property blocks required in large and complex system-on-chips. In this paper, we propose a new NoC architecture, referred as the Quartered Recursive Diagonal Torus (QRDT), which is constructed by overlaying diagonal torus. Due to its small diameter and rich routing recourses, QRDT is determined to be well suitable to construct highly scalable NoCs.

In this paper, we propose a highly scalable network architecture, named the Progressive Multi-hop Rotational Clus- tered (PMRC) structure, suitable for the construction of large- scale wireless sensor networks. In the PMRC structure, sensor nodes are partitioned into layers according to their distances (cal- culated using hop counts) to the sink node. A cluster is composed of the nodes located in the same layer and within the transmission range of the cluster head which is located in one layer up. Each cluster here actually selects two cluster heads, which makes the PMRC structure different from another multi-layered structure, MINA (4). Based on the observation that load balancing tends to help balance the energy consumption among different sensor nodes and consequently prolong the network life time, we further propose a rotational scheme functioning at two levels: 1) the two cluster heads in the same cluster rotate to receive and forward data, and 2) clusters at the same layer rotate to sense data. Exten- sive simulations have been conducted to verify the rotation scheme with two selection strategies each specially tailored for one of the two cluster heads required in the PMRC structure. These results have confirmed that the PMRC structure and its rotation scheme together can significantly prolong the node life time and reduce the number of network reconstructions compared with those obtained from a multi-layered structure with single cluster head. I. INTRODUCTION The benefits of low-cost, rapid deployment, self-organization capa- bility and cooperative data-processing have made the wireless sensor networks a practical solution for a wide range of application areas, including military, industry and commercial, environment, health and home (2), (3). The most significant challenge in sensor networks is to overcome the energy constraint since each sensor node has limited power ( ) and it is hard to replenish the power es- pecially in hazardous or hostile application scenarios. The other chal- lenge faced by sensor networks is scalability. Many applications, such as military surveillance and habitat monitoring, require the deploy- ment of large-scale sensor networks (with the number of sensor nodes in the order of hundreds or thousands, or even millions) in a large ge- ographic area, and seamless connectivity to existing infrastructures is usually required when new nodes are added. Other research work for large-scale sensor networks include (7) and (10). In (7), the SAFE protocol was proposed for data dissemination from stationary sensor nodes to mobile sink nodes in large-scale sen- sor networks. The major problems of the SAFE protocol are the large number of states to be maintained at intermediate nodes and the mul- tiple rounds of message exchanges required to set up a path. The two- tier data dissemination (TTDD) protocol (10) is another protocol for disseminating data from stationary sensor nodes to multiple mobile sinks by setting up a grid structure. However, the cost of proactively creating/maintaining the grid structure from all sources to the edge of the sensor field tends to be unbearably high for large sensor networks. In this paper, we follow the layered structure and subsequently pro- pose the Progressive Multi-hop Rotational Clustered (PMRC) struc- ture as an extension to the MINA structure (4). In a PMRC structure, a cluster is formed in the way similar to that in MINA but with a signif- icant distinction: here two cluster heads are selected for each cluster. To balance the load and the energy consumption among different sen- sor nodes, we propose a rotational scheme functioning at two levels: 1) the two cluster heads in the same cluster rotate to receive and forward data, and 2) clusters at the same layer rotate to sense data. Through simulations, we show that the PMRC structure together with its ro- tational scheme outperforms the multi-layered structure with single cluster head in node life time and hence reduce the number of network reconstructions. The rest of the paper is organized as follows. In Section II, we will describe the PMRC structure. In Section III, the problems and algo- rithms of selecting the primary cluster head and the secondary cluster head are discussed. In Section IV, simulation results are presented and discussed. Section V concludes the paper.

In communication networks, multiple communication paths sharing minimum number of links or/and nodes may be desirable for improved performance, resource utilization and reliability. We introduce the notion of link sharability and node sharability, and consider the problems of finding minimum-cost k paths subject to minimum link/node sharability constraints. We identify 65 different link/node sharability constraints, and consider the fundamental problem of finding minimum-cost k paths between a pair of nodes under these constraints. We present a unified polynomial-time algorithm scheme for solving this problem subject to 25 of these different sharability constraints.

The Distributed Denial-of-Service (DDoS) attack is a serious threat in the Internet, and an effective method is needed for distinguishing the attack traffic from the legitimate traffic. In DDoS attacks, the large volume of attack streams cause self-induced congestion or higher utilization of the links. Based on this observation, we propose the Congestion Path Marking (CPM) scheme to identify and drop the attack packets. In this proposed scheme, we store the link utilization information in the packet header so that suspicious attack packets can be distinguished. Each router along the path records its local congestion information, and this information is accumulated to represent the overall congestion level that a packet has experienced. To enable light-weight real-time processing, we employ a RED-like random packet dropping mechanism at the victim's egress router. Through simulations, we show that when the CPM scheme is employed, most of the attack packets in excess of the link capacity are dropped while less than 4% of the legitimate packets are dropped in typical scenarios. The simulation result also shows significantly improved TCP performance when CPM is utilized.

In this paper, we propose a scalable multicast protection scheme based on a dual-homing architecture where each destination host is connected to two edge routers. Under such an architecture, there are two paths from the source of a multicast session to each destination host, which provides a certain level of protection for the data traffic from the source to the destination host. The protection level varies from 0 percent to 100 percent against a single link failure, depending on the number of shared links between these two paths. The major advantage of the proposed scheme lies in its scalability due to the fact that the protection is provided by constructing a dual-homing architecture at the access network while keeping the routing protocols in the core network unchanged. The selection of dual edge routers plays an important role in enhancing the protection level. Two problems arise for the proposed dual-homing partial multicast protection scheme. One is to calculate the survivability from the source to any pair of edge routers. The other is to assign a pair of edge routers for each destination host such that the total survivability is maximized for the multicast session subject to the port number constraint of each edge router. We propose an optimal algorithm to solve the first problem. We prove the decision version of the second problem is NP-complete and propose two heuristic algorithms to solve it. Simulation results show that the proposed heuristic algorithms achieve performance close to the calculated lower bound

Nonblocking interconnection networks are always favored to be used as switching networks whenever possible. The crosstalk-free requirement in photonic networks adds a new dimension of constraints for nonblockingness. Routing algorithms play a fundamental role in nonblocking networks, and any algorithm that requires more than linear time would be considered too slow for real-time applications. One remedy is to use multiple processors to route connections in parallel and the other is to construct cost effective self-routing nonblocking networks. We propose a new class of self-routing strictly nonblocking networks by studying the connection capacity of banyan-type networks. Compared with existing strictly nonblocking self-routing networks, the presented new networks have lower hardware cost, shorter connection diameter, and much smaller number of required wavelengths. Consequently, they are more feasible for implementation with reduced optical signal attenuation and crosstalk.

We propose a novel multicast protection scheme based on a dual-homing architecture where each destination host is connected to two edge routers. Under such an architecture, the two paths from the source of the multicast session to the two edge routers provide certain protection for the data traffic from the source to the destination host. Two problems are associated with the proposed dual-homing multicast protection scheme. One is to calculate the individual survivability for a destination host that is connected to two edge routers. The other is to assign two edge routers for each destination host such that the total survivability is maximized for the multicast session subject to the port number constraint of edge routers. We propose an optimal algorithm to solve the first problem and a heuristic algorithm to solve the second problem. Through simulations, we show that the proposed heuristic algorithm achieves a performance close to the calculated lower bound.

Due to its simplicity and scalability, the differentiated services (DiffServ) model is expected to be widely deployed across the Internet. For each DiffServ compliant router, the scheduling algorithm is critical in implementing per hop behaviors (PHBs), according to which packets are forwarded. We propose a hierarchical DiffServ scheduling (HDS) algorithm to support DiffServ classes on input-queued switches. The proposed HDS algorithm features in a hierarchical scheduling scheme that consists of two levels of schedulers. One level is the central scheduler which is designed to maximize the switch throughput by computing a maximal size matching between input ports and output ports. The other level is formed by input port schedulers which provide differentiated services by serving cells belonging to different classes dynamically. Using such a hierarchical scheme, the implementation complexity and the amount of information needed to be transmitted between input ports and the central scheduler are dramatically reduced compared with existing maximal weight matching based DiffServ scheduling algorithms. The tradeoff of its slightly worse delay performance is acceptable.

Applications of stable matching in switch scheduling have been proposed. However, the classical GS (Gale and Shapley) stable matching algorithm is infeasible for high-speed implementation due to its high complexity. Instead, acyclic stable matching algorithms have been shown useful in implementing scheduling for high-speed switches/routers. We model the acyclic stable matching problem as the dominating set problem for a rooted dependency graph, and propose a parallel algorithm for finding the dominating set in O(n log n) time. We design and implement a scheduler based on the proposed algorithm in hardware. Simulation results show that the number of 2-input NAND gates and the timing of our design are proportional to n/sup 2/ and n respectively, making it feasible to implement the scheduler at high speed with current CMOS technologies.

The diverse service requirements of emerging Internet applications faster the need for flexible and scalable IP quality-of-service (QoS) schemes. Due to its simplicity and scalability, DiffServ is expected to be widely deployed across the Internet. Though DiffServ supporting scheduling algorithms for output-queueing (OQ) switches have been widely studied, there are few DiffServ scheduling algorithms for input-queueing (IQ) switches. In this paper, we propose the dynamic DiffServ scheduling (DDS) algorithm for IQ switches to provide dynamic bandwidth allocation for DiffServ classes. The basic idea of DDS is to schedule EF and AF traffic according to their minimum service rates with the reserved bandwidth and schedule AF and BE traffic fairly with the excess bandwidth. We evaluate the performance of DDS under bursty traffic arrivals and compare it with PQWRR, an existing scheduling algorithm suitable for supporting DiffServ for OQ switches. Simulations results show that DDS provides minimum bandwidth guarantees for EF and AF traffic and fair bandwidth allocation for BE traffic. DDS also achieves the delay and jitter performance for EF traffic close to that of PQWRR and the delay performance for AF traffic better than that of PQWRR at high loads. Using comparator-tree based arbitration components, it is feasible to implement DDS in hardware at high speed.

Recently, CIOQ switches have attracted interest from both academic and industrial communities due to their ability of achieving 100% throughput and perfectly emulating OQ switch performance with a small speedup factor S. To achieve a speedup factor S, a conventional CIOQ switch requires the switch matrix and the memory to operate S times faster than the line rate. In this paper, we propose to use a CIOQ switch with space-division multiplexing expansion and grouped inputs/outputs (SDMG CIOQ switch for short) to achieve speedup while only requiring the switch matrix and the memory to operate at the line rate. The cell scheduling problem for the SDMG CIOQ switch is abstracted as a maximum bipartite k-matching problem. Using fluid model, we prove that any maximal size k-matching algorithm on an SDMG CIOQ switch with an expansion factor 2 can achieve 100% throughput assuming input arrivals satisfy the strong law of large numbers and no inputs/outputs are oversubscribed. We further propose an efficient and starvation-free maximal size k-matching scheduling algorithm, kFRR, for the SDMG CIOQ switch. Simulation results show that kFRR achieves 100% throughput with an expansion factor 2 under two SLLN traffic models, uniform traffic and polarized traffic, confirming our analysis.

In this paper, we propose new pipelined request-grant-accept (RGA) and request-grant (RG) maximal size matching (MSM) algorithms to achieve speedup in combined input and output queueing (CIOQ) switches. To achieve a speedup factor S, in the proposed pipelined RGA/RG MSM algorithms, we pipeline operations of finding S matching in S scheduling cycles based on the observation that all matched inputs/outputs will not be used in later iterations in the same scheduling cycle. We show that our pipelined RGA/RG MSM algorithms reduce the scheduling time constraint by SI/(I+S-1), where I is the number of iterations allowed in each scheduling cycle. Taking the example of pipelined PIM, we evaluate the performance of the proposed algorithms by simulation. Simulation results have shown that pipelined PIM for CIOQ switches with speedup of 2 under both Bernoulli and bursty arrivals.

DSP processors have gained more importance and popularity in implementing communication systems. Efficient implementation of logarithm and arctangent functions on DSP processors is necessary for applications such as digital receiver used in modern radar systems and digital communication systems. This paper presents a general scheduling and mapping optimization method based on grain packing to implement the two functions on TI TMS320C67X architecture with multiple parallel function units. Experimental results of our optimized implementation on TMS320C67x have achieved up to 79.5% performance improvement over TI C67x library functions. Our optimization method and techniques can also be applied to other DSP processors with parallel execution units.

The ubiquity of IP has led to IP-over-WDM as the core architecture for the next-generation optical Internet. Optical burst switching (OBS) has been proposed to be a competitive switching technology for DWDM networks. The data channel scheduling algorithm is one of the major challenges in OBS. The same-service-to-all model of the current Internet is inadequate for the diverse quality of service expectations of Internet applications and users. Differentiated service (DiffServ) was proposed to provide a scalable and manageable architecture for service differentiation in IP networks. This paper proposes a scheduling algorithm based on an existing LAUC-VF algorithm to support DiffServ and takes advantage of MPLS. Simulation results demonstrate that this algorithm has better QoS performance than the existing LAUC-VF algorithm.