Search

In this paper, we present two algorithms for efficiently aggregating link state information needed for quality-of-service (QoS) routing. In these algorithms, each edge node in a group is mapped onto a node of a shufflenet or a node of a de Bruijn graph. By this mapping, the number of links for which state information is maintained becomes aN (a is an integer, N is the number of edge nodes) which is significantly smaller than N2 in the full-mesh approach. Our algorithms also can support asymmetric link state parameters which are common in practice, while many previous algorithms such as the spanning tree approach can be applied only to networks with symmetric link state parameters. Experimental results show that the performance of our shufflenet algorithm is close to that of the full-mesh approach in terms of the accuracy of bandwidth and delay information, with only a much smaller amount of information. On the other hand, although it is not as good as the shufflenet approach, the de Bruijn algorithm also performs far better than the star approach which is one of the most widely accepted schemes. The de Bruijn algorithm needs smaller computational complexity than most previous algorithms for asymmetric networks, including the shufflenet algorithm.

In most existing studies of wavelength-division multiplexing networks, the problems of routing and wavelength assignment are generally treated separately, since it is NP-complete to produce the optimal solutions for the two problems at the same time. The four presented adaptive routing algorithms, however, consider the availability of wavelengths during the routing process. Our algorithms favor paths with the near-maximum number of available wavelengths between two nodes, resulting in improved load balancing. Simulations show that our algorithms reduce call blocking by nearly half when compared with the least-loaded and the k-fixed routing algorithms in some small networks using the first-fit wavelength assignment policy. In addition, simulation and analysis show that the path length of our algorithms is almost the same as those of the other algorithms.

A new dynamic buffer allocation strategy based on the notion of marginal gains is presented for the buffer cache that is used by the operating system to store frequently accessed disk blocks in main memory, and the performance of the proposed strategy is compared with those of previous allocation strategies. In the proposed strategy, marginal gain values are predicted by exploiting functions that approximate the expected number of buffer hits per unit time. Experimental results from both trace-driven simulation and an actual implementation in the FreeBSD operating system show that the proposed strategy accurately predicts the marginal gain values for various workloads resulting in significantly improved buffer hit ratios.

Efficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full. In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and {\rm O}(\log_2 n) (the time complexity of LFU), where n is the number of blocks in the buffer. Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered.

Cache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in realtime computing systems where predictability is of utmost importance. We propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and 18 percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues.

Sam H. Nohs Sang Lyul Mint t Department of Computer Engineering Seoul National University Seoul 151-742, Korea http://ssrnet.snu.ac.kr http://archi.snu.ac.kr We show that there exists a spectrum of block replacement policies that subsumes both the Least Recently Used (LRU) and the Least Frequently Used (LFU) policies. The spectrum is formed according to how much more weight we give to the recent history than to the older history, and is referred to as the LRFU (Least Recently/Frequently Used) policy. Unlike many previous policies that use limited history to make block replacement decisions, the LRFU policy uses the complete reference history of blocks recorded during their cache residency. Nevertheless, the LRFU requires only a few words for each block to maintain such history. This paper also describes an implementation of the LRFU that again subsumes the LRU and LFU implementations. The LRFU policy is applied to buffer caching, and results from trace-driven simulations show that the LRFU performs better than previously known policies for the workloads we considered. This point is reinforced by results from our integration of the LRFU into the FreeBSD operating system.

In multi-tasking real-time systems, inter-task cache interference due to preemptions degrades schedulability as well as performance. To address this problem, we propose a novel scheduling scheme, called limited preemptive scheduling (LPS), that limits preemptions to execution points with small cache-related preemption costs. Limiting preemptions decreases the cache-related preemption costs of tasks but increases blocking delay of higher priority tasks. The proposed scheme makes an optimal trade-off between these two factors to maximize the schedulability of a given task set while minimizing cache-related preemption delay of tasks. Experimental results show that the LPS scheme improves the maximum schedulable utilization by up to 40\% compared with the traditional fully preemptive scheduling (FPS) scheme. The results also show that up to 20\% of processor time is saved by the LPS scheme due to reduction in the cache-related preemption costs. Finally, the results show that both the improvement of schedulability and the saving of processor time by the LPS scheme increase as the speed gap between the processor and main memory widens.

This paper proposes a cost-effective solution to the virtual cache synonym problem. In the proposed solution, a minimal hardware addition guarantees correct handling of the synonym problem whereas a simple modification to the virtual-to-physical address mapping in the operating system optimizes the performance. The key to the proposed solution is a small, physically-indexed cache called a U-cache. The U-cache maintains the reverse translation information of cache blocks that belong to unaligned virtual pages, where unaligned means that the lower bits of the virtual page number that are used to index the virtual cache do not match those of the corresponding physical page number. The biggest advantage of the U-cache approach is that it leaves room for software optimization in the form of mapping alignment. Performance evaluation based on memory reference traces from a real system shows that the U-cache, with only a few entries, performs almost as well as (in some cases outperforms) a fully-configured hardware-based solution when more than 95% of mappings are aligned.

We propose a new framework for the link assignment (i.e., topological design) problem that arises from the use of intersatellite links (ISL's) in low-earth orbit (LEO) satellite networks. In the proposed framework, we model an LEO satellite network as a finite state automaton (FSA), where each state corresponds to an equal-length interval in the system period of the LEO satellite network. This FSA-based framework allows the link assignment problem in LEO satellite networks to be treated as a set of link assignment problems in fixed topology networks. Within this framework, we study various link assignment and routing schemes. In particular, both regular link assignment and link assignment optimized by simulated annealing are considered. For each link assignment, both static and dynamic routing schemes are considered. Our simulation results show that the optimized link assignment combined with static routing achieves the best performance in terms of both newly initiated call blocking probability and ongoing call blocking probability. The results also show that when the link assignment is the same, static routing gives better performance than dynamic routing since the latter requires a substantial amount of time to stabilize its routing table after a state transition.

Recent advances in VLSI technology have made it possible to use large enough caches to eliminate most of the “conventional” cache misses resulting from limited cache size and/or set associativity. As a result, other sources of “non-conventional” cache misses are becoming increasingly dominant in the makeup of the total cache misses. One of those sources is the clearing of remapped physical pages by the operating system, which is required for security reasons. Our experiment shows that the traditional method of “overeager” clearing of remapped physical pages results in up to 13% of the total data cache misses. In this paper, we propose a novel method of page clearing to reduce such high cache overhead. Our scheme is based on “on-demand”, “in-cache” page clearing and can be implemented efficiently on existing hardware. Our trace-driven simulation based on multitasking traces indicates that the proposed scheme can reduce up to 7% of the total data cache misses and up to 16% of the total stalls related to data access

Cache memories have been extensively used to bridge the speed gap between high speed processors and relatively slow main memory. However, they are not widely used in real-time systems due to their unpredictable performance. This paper proposes an instruction prefetching scheme called threaded prefetching as an alternative to instruction caching in real-time systems. In the proposed threaded prefetching, an instruction block pointer called a thread is assigned to each instruction memory block and is made to point to the next block on the worst case execution path that is determined by a compile-time analysis. Also, the thread is not updated throughout the entire program execution to guarantee predictability. This paper also compares the worst case performances of various previous instruction prefetching schemes with that of the proposed threaded prefetching. By analyzing several benchmark programs, we show that the worst case performance of the proposed scheme is significantly better than those of previous instruction prefetching schemes. The results also show that when the block size is large enough the worst case performance of the proposed threaded prefetching scheme is almost as good as that of an instruction cache with 100 % hit ratio.

An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each program construct is a simple time bound. In our approach, associated with each program construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. The paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach. >

Predictable performance is crucial for real-time computing systems. We propose a buffered threaded prefetch scheme as a predictable and high performance instruction memory hierarchy. We also give extensions to the timing schema[3] to analyze the timing effects of the proposed scheme. In the extended timing schema, we associate with each program construct what we call a WCTA (Worst Case Timing Abstraction), which contains detailed timing information of the program construct. By defining a concatenation operation on WCTAs, our revised timing schema accurately accounts for the timing effects of the buffered threaded prefetching not only within but also across program constructs. This paper shows, through analysis using a timing tool based on the extended timing schema, the buffered prefetch scheme significantly improves the worst case execution times of tasks.

We propose and analyze an adaptive instruction prefetch scheme, called threaded prefetching, that makes use of history information to guide the prefetching. The scheme is based on the observation that control flow paths are likely to repeat themselves. In the proposed scheme, we associate with each instruction block a number of threads that indicate the instruction blocks that have been brought into the cache by the current block. These threads later trigger the prefetching of the indicated instruction blocks once the instruction block containing them are re-accessed by the processor. These pointers, in effect, encode the causal relationship between an instruction block and the instruction blocks that have been brought into the cache by the block. The results from trace-driven simulations using SPEC benchmarks show that the proposed scheme improves the prefetch accuracy by more than 100% on average for 32 Kb cache. They also show that the scheme significantly (80% on average for 32 Kb cache) improves the CPI (Clocks Per Instruction) due to instruction references over the sequential prefetching.

This paper proposes a new optical path restoration method for wavelength division multiplexing (WDM) networks. In the method, the protection path is established by connecting several sub-lightpaths from the source node to the destination node of the original working lightpath, as opposed to conventional path restoration where a single protection lightpath between the source-destination pair performs restoration. The set of one or more consecutive lightpaths to connect a source-destination pair is called semi-lightpath. The semi-lightpath based restoration provides enhanced flexibility in protection path provisioning and relieves the cost of spare capacity reservation and wavelength conversion at intermediate optical cross-connect nodes. In terms of spare capacity utilization, our method shows substantial reduction of spare capacity overhead compared with dedicated path restoration in all optical networks without wavelength conversion, and shows similar capacity efficiency compared with shared path restoration in opaque networks with full wavelength conversion capability.

This paper studies the robustness of link restoration algorithms using multiple ring-covers for mesh networks. We have presented the trade-off between the capacity overhead and the robustness and also the robustness of each restoration group. The results indicates that multi-level reliability services according to priorities or QoS requirements of traffic can be feasible using multiple ring-covers.

The three adaptive algorithms proposed in this paper address the routing and the wavelength assignment problems at once. They search for a route with the near-maximum number of available wavelengths between two nodes, resulting in the improvement of load balancing. Simulation results show that our algorithms improve blocking probability by up to 50%, compared to the least-loaded and the k-fixed routing algorithms. In addition, the path length of our algorithms is almost equal to that of the others according to the simulation and analysis.

One of the obstacles to using RISC processors in a hard real-time environment is the unpredictability of caches. This unpredictability stems from basing them on a design that tries to optimize the average case execution time. We propose a dual mode instruction prefetch scheme as an alternative to instruction caching schemes. In the proposed scheme, a thread is associated with each instruction block. The thread indicates the instruction block that is to be prefetched once the block containing it is accessed by the processor. The proposed scheme operates in two different modes: real-time and non real-time modes. In the real-time mode, the prefetching of instruction blocks is made in the direction that improves the worst case execution time. For this purpose, the thread is generated by the compiler through an analysis of the worst case execution path. In the non real-time mode, the thread is dynamically updated so that it indicates the instruction block that is most likely to be accessed next is the block that was previously accessed after the present block. Therefore, the thread is made to point to such a block in the non real-time mode. The above tailoring of thread information is on a task basis and, therefore, each task in the system can choose its own mode depending on its needs. Typically real-time tasks choose the real-time mode for an improved worst case execution time whereas non time critical tasks choose the non real-time mode for an improved average case execution time. This paper shows, through analysis using a timing tool, that the proposed scheme significantly (up to 45%) improves the predicted worst case execution time in the real-time mode as compared with no prefetching scheme. >

We propose an enhanced technique for analyzing, and thus bounding cache related preemption delay in fixed priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache related preemption delay. Second, the technique considers phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache related preemption delay. The paper also compares the proposed technique with previous techniques. The results show that the proposed technique gives up to 60% tighter prediction of the worst case response time than the previous techniques.

We compare the performance of two routing schemes for LEO satellite networks through simulation. The two routing schemes represent static and dynamic routing for the case where the LEO satellite network is modeled as a finite state automaton (FSA). Each state in this FSA modeling corresponds to an equal-length interval within the period of the LEO satellite network. Modeling the LEO satellite network in this way allows us to consider the LEO satellite network as if it is a fixed topology network within each state. The routing table for the static routing is fixed within each state whereas that for the dynamic routing is updated continuously according to the shortest-path algorithm. The simulation results show that the static routing performs better in terms of newly initiated call blocking than the dynamic one. The results also show that the static routing gives lower ongoing call blocking probabilities than the dynamic counterpart since the former's pre-computed routing table is less susceptible to the abrupt topological change during a state transition.

Proposes a new competitive learning algorithm that dynamically creates output neurons. The number of output neurons is increased as learning proceeds, whereas conventional competitive learning algorithms use all of the available output neurons during the entire learning phase. An acceptance test for the winning output neuron is performed using class thresholds if the number of created output neurons is less than the predefined maximum number. Accepted input vectors are used to adjust the reference vector of the winning output neuron. If an input vector is rejected, it is used as the initial reference vector of a new output neuron. The proposed method gets around the drawbacks of the conventional competitive learning algorithms by changing the class threshold values of output neurons dynamically. Experiments with remote sensing data and speech data indicate the superiority of the proposed algorithm in comparison to the conventional competitive learning methods. >

In large-scale shared-memory multiprocessors, the delayed consistency memory models are efficient for tolerating the large latency of the processor-memory interconnection network. In the delayed consistency memory models most of the write requests do not block the processor whereas the read requests do, so the read requests are more urgent than the write requests are. If an urgent read request is blocked by less urgent write requests in the processor-memory interconnection network, priority inversion arises because the read request should have a higher priority than the write requests. We show the priority inversion effects on the performance of the shared-memory multiprocessors, and demonstrate how much the performance can be improved by removing the priority inversion. With a performance analysis based on simulations, we could observe that removing the priority inversion speeds up the execution of parallel programs especially when the bandwidth of the interconnection network is small and the cache miss rate of a parallel program is high. >

Survivability is one of the important issues in broadband networks, since even a single network element failure may cause a serious amount of data loss. There have been two main approaches for connection restoration: dynamic approach and backup approach. We discuss the trade-offs between the two approaches and propose a new restoration mechanism that centers around the concept of the virtual backup network, which provides backup path sharing as well as spare bandwidth sharing. The proposed mechanism can take advantage of the two existing approaches together with special interests in resource efficiency and routing flexibility.