The problem of record linkage is to cluster the records from several data sources such that each cluster has all the records belonging to one and only one entity. Record linkage has applications in a wide variety of domains including public health, law enforcement, fraud detection, biology, and transportation. Given the typically vast sizes of datasets, existing algorithms suffer from very long runtimes. Hence, it is essential to develop novel algorithms tailored to address this issue. Blocking is a popular technique employed to speed up record linkage algorithms. In this paper, we employ a blocking technique that is based on Soundex encoding. Soundex index is a method of coding names based on their pronunciation rather than their spelling. Soundex has been traditionally used only as a distance metric. In this paper, we show how to use Soundex as a blocking technique. To the best of our knowledge, no one else has done it in the past. In fact, we introduce two novel blocking approaches that utilize Soundex encoding: One stage Soundex blocking and Two stage Soundex blocking.Our approaches exhibit superior linkage performance compared to the state-of-the-art record linkage algorithms, as evidenced by higher F-1 scores and reduced linkage times. The proposed blocking approaches prove to be highly effective.

Given multiple data sets, the problem of record linkage is to cluster them such that each cluster has all the information pertaining to a single entity and does not contain any other information. This problem has numerous applications in domains such as healthcare, law enforcement, medicine, census data analysis, etc. The performance of record linkage algorithms is measured with two metrics, namely, run times and accuracy. Record linkage has been studied extensively and numerous algorithms have been proposed. These algorithms take a very long time especially when the input data sets are large. Many applications of interest call for real-time or very nearly real-time performance. Thus there is a crucial need for the creation of novel record linkage algorithms that are very fast while maintaining a very good accuracy.Blocking is a technique that is typically used to speed up record linkage algorithms. In this paper, we introduce a novel algorithm for blocking called SuperBlocking. We have created novel record linkage algorithms that employ SuperBlocking. Experimental comparisons reveal that our algorithms outperform state-of-the-art algorithms for record linkage. We have also developed parallel versions of our record linkage algorithms and they obtain close to linear speedups.

We develop an algorithm to find walks in contact sequence temporal graphs that have no cycle whose duration is zero. These walks minimize any specified linear combination of optimization criteria such as arrival time, travel duration, hops, and cost. The algorithm also accommodates waiting time constraints. When min and max waiting time constraints are specified, the complexity of our algorithm is$O(\vert V\vert +\vert E\vert\delta)$, where$\vert V\vert$is the number of vertices,$\vert E\vert$is the number of edges, and$\delta$is the maximum out-degree of a vertex in the contact sequence temporal graph. When there are no maximum waiting time constraints, the complexity of our algorithm is$O(\vert V\vert +\vert E\vert)$. On the test data used by Bentert et al., our optimal walks algorithm provides a speedup of up to 77 over the algorithm of Bentert et al. [1] and a memory reduction of up to 3.2.

We propose a new time-respecting data structure (TRG) for contact sequence temporal graphs that is more memory efficient than previously proposed TRGs. Our new TRG alters the balance between TRG structures and the ordered sequence of edges (OSE) data structure. While TRG structures have an obvious performance advantage over OSE for problems that can be solved via a shallow neighborhood search, previous research has shown that single-source all-destinations problems are more effectively solved using OSE. The competitiveness of our TRG structure for this class of problems is demonstrated for the single-source all-destinations fastest paths and min-hop paths problems. Our TRG structure retains the advantage that other similar structures have over OSE for shallow neighborhood search problems.

We develop algorithms for foremost paths and min-hop paths in interval temporal graphs. These algorithms are benchmarked against the fastest algorithms known for foremost and min-hop paths in contact sequence temporal graphs. On our test data, our foremost path algorithm provides a speedup of up to 1800 over the fastest algorithm for contact sequence graphs; the speedup for our min-hop algorithm is up to 6700. We also demonstrate path problems that are NP-hard in the interval temporal graph model but polynomial in the contact sequence temporal graph model.

This paper focuses on the data aggregation problem to two aggregators in a data center network under the constraint that each source rack must use a single path to each aggregator. We derive bounds on the approximation ratios of two classes of aggregation algorithms- Restricted 1-Round (R1R) and Restricted 2-Round (R2R). We achieve tighter bounds for the problem with additional constraints on the inputs. We propose another strategy using the 2Chain topology for k = 2, where k denotes the maximum degree of each top-of-rack(ToR) switch (number of uplinks in a ToR switch) in the data center and show that the optimal 2Chain cannot have an aggregation time greater than that of the optimal R1R and R2R topologies. For k ≥ 4, we propose a 1-round aggregation algorithm (1R) that uses trees for aggregation. Experimental results illustrate that 1R, R2R and R1R reduce the aggregation time by up to 85, 67 and 67 percent respectively for k = 4 relative to the two-round aggregation algorithm proposed by Wang et al. Moreover, for k = 2, the 2Chain can reduce the aggregation time up to 42 and 24 percent respectively relative to R1R and R2R.

We develop efficient single-and multi-core algorithms to compute partition functions for RNA sequences.Our algorithms, which are based on McCaskill's algorithm, are benchmarked against state-of-the-art fast algorithms obtained using the parallelizing source-to-source compilers PLUTO and TRACO.On our Intel I9 computational platform, our best single core algorithm takes up to 81.2% less time than the single core algorithm resulting from PLUTO, which is faster than that obtained from TRACO.Our best multi-core algorithm takes up to 84.7% less time than the multi-core algorithm obtained using TRACO when run with 20 threads (our I9 has 10 cores and supports hyperthreading); the TRACO multi-core algorithm is faster than the PLUTO one.

We develop a cache efficient Louvain community detection algorithm. Its effectiveness is demonstrated by bench-marking it against four existing Louvain algorithms on the Intel Knights Landing (KNL) and Haswell computational platforms using real and synthetic datasets. For a single iteration of Louvain, our algorithm obtains a speedup of up to 76.18% on real datasets on KNL, 51.91% on real networks on Haswell, 71.31% on synthetic networks on KNL, and 59.13% on synthetic networks on Haswell. These percentages using 2 iterations are 62.91%, 43.27%, 67.61%, and 54.43%, respectively.

BACKGROUND: The Damerau-Levenshtein (DL) distance metric has been widely used in the biological science. It tries to identify the similar region of DNA,RNA and protein sequences by transforming one sequence to the another using the substitution, insertion, deletion and transposition operations. Lowrance and Wagner have developed an O(mn) time O(mn) space algorithm to find the minimum cost edit sequence between strings of length m and n, respectively. In our previous research, we have developed algorithms that run in O(mn) time using only O(s∗min{m,n}+m+n) space, where s is the size of the alphabet comprising the strings, to compute the DL distance as well as the corresponding edit sequence. These are so far the fastest and most space efficient algorithms. In this paper, we focus on the development of algorithms whose asymptotic space complexity is linear. RESULTS: We develop linear space algorithms to compute the Damerau-Levenshtein (DL) distance between two strings and determine the optimal trace (corresponding edit operations.)Extensive experiments conducted on three computational platforms-Xeon E5 2603, I7-x980 and Xeon E5 2695-show that, our algorithms, in addition to using less space, are much faster than earlier algorithms. CONCLUSION: Besides using less space than the previously known algorithms,significant run-time improvement was seen for our new algorithms on all three of our experimental platforms. On all platforms, our linear-space cache-efficient algorithms reduced run time by as much as 56.4% and 57.4% in respect to compute the DL distance and an optimal edit sequences compared to previous algorithms. Our multi-core algorithms reduced the run time by up to 59.3% compared to the best previously known multi-core algorithms.

Value Iteration (VI) is a powerful, though time consuming, approach to solve Markov Decision Processes (MDPs). Exisitng algorithms for VI incur a large number of cache misses. Motivated by the observation that, on modern computers, the cost of a cache miss is two to three orders of magnitude more than that of an arithmetic operation, we explore the possibility of improving the performance of VI by reducing the number of cache misses, possibly at the expense of increasing the number of backups. We demonstrate experimentally that the strategies proposed by us, in this paper, to improve the cache efficiency of VI result in speedups of up to a factor of 3.7 when incorporated into state-of-the-art VI software.

BACKGROUND: In the string correction problem, we are to transform one string into another using a set of prescribed edit operations. In string correction using the Damerau-Levenshtein (DL) distance, the permissible edit operations are: substitution, insertion, deletion and transposition. Several algorithms for string correction using the DL distance have been proposed. The fastest and most space efficient of these algorithms is due to Lowrance and Wagner. It computes the DL distance between strings of length m and n, respectively, in O(mn) time and O(mn) space. In this paper, we focus on the development of algorithms whose asymptotic space complexity is less and whose actual runtime and energy consumption are less than those of the algorithm of Lowrance and Wagner. RESULTS: We develop space- and cache-efficient algorithms to compute the Damerau-Levenshtein (DL) distance between two strings as well as to find a sequence of edit operations of length equal to the DL distance. Our algorithms require O(s min{m,n}+m+n) space, where s is the size of the alphabet and m and n are, respectively, the lengths of the two strings. Previously known algorithms require O(mn) space. The space- and cache-efficient algorithms of this paper are demonstrated, experimentally, to be superior to earlier algorithms for the DL distance problem on time, space, and enery metrics using three different computational platforms. CONCLUSION: Our benchmarking shows that, our algorithms are able to handle much larger sequences than earlier algorithms due to the reduction in space requirements. On a single core, we are able to compute the DL distance and an optimal edit sequence faster than known algorithms by as much as 73.1% and 63.5%, respectively. Further, we reduce energy consumption by as much as 68.5%. Multicore versions of our algorithms achieve a speedup of 23.2 on 24 cores.

In this paper we focus on the problem of data aggregation using two aggregators in a data center network, where the source racks are allowed to split their data and send to the aggregators using multiple paths. We show that the problem of finding a topology that minimizes aggregation time is NP-hard fork = 2, 3, 4, where k is the maximum degree of each ToR switch (number of uplinks in a top-of-rack switch) in the data center. We also show that the problem becomes solvable in polynomial time fork = 5 and 6 and conjecture the same for k > 6. Experimental results show that, for k = 6, our topology optimization algorithm reduces the aggregation time by as much as 83.32 percent and reduces total network traffic by as much as 99.5 percent relative to the torus heuristic, proposed in [1], which readily proves the significant improvement in performance achieved by the proposed algorithm.

Hybrid multicore processors (HMPs) are poised to dominate the landscape of the next generation of computing on the desktop as well as on exascale systems. HMPs consist of general purpose CPU cores along with specialized co-processors and can provide high performance for a wide spectrum of applications at significantly lower energy requirements per FLOP. In this paper, we develop parallel algorithms and software for constructing multi-resolution SAR images on HMPs. We develop several load balancing algorithms for optimizing time performance and energy on HMPs. We also present a systematic approach for deriving the energy-time performance trade-offs on HMPs in the presence of Dynamic Voltage Frequency Scaling. Pareto-optimal curves are presented on a system consisting of 24 traditional cores and a GPU.

Data aggregation is a critical operation in many big-data applications; for example, data residing in several source racks (mappers) are to be aggregated into one or more specified racks called aggregators (reducers) in the data center network during the shuffle phase of a map-reduce task. In this paper, we explore algorithms for data aggregation to two aggregators in a data center network under the constraint that data from a source rack must be routed to each aggregator using a single path. We derive bounds on the approximation ratios of two classes of aggregation algorithms- Restricted 1-Round (R1R) and Restricted 2-Round (R2R). For the case when racks have exactly 2 optical links (uplinks in Top-of-Rack switches), we propose another strategy using the 2Chain topology for aggregation and show that the optimal 2Chain cannot have an aggregation time greater than that of the optimal R1R and R2R topologies. For the case when racks have at least 4 optical links, we propose a 1-round aggregation algorithm (1R) that uses tree topology for aggregation. Experimental results indicate that, when racks have 4 optical links, 1R, R2R and R1R reduce the aggregation time by up to 85%, 67% and 67% respectively, relative to the two-round aggregation algorithm proposed by Wang et al. Moreover, the 2Chain can reduce the aggregation time up to 42% and 24% respectively relative to R1R and R2R, when racks have exactly 2 optical links.

BACKGROUND: An RNA folding/RNA secondary structure prediction algorithm determines the non-nested/pseudoknot-free structure by maximizing the number of complementary base pairs and minimizing the energy. Several implementations of Nussinov's classical RNA folding algorithm have been proposed. Our focus is to obtain run time and energy efficiency by reducing the number of cache misses. RESULTS: Three cache-efficient algorithms, ByRow, ByRowSegment and ByBox, for Nussinov's RNA folding are developed. Using a simple LRU cache model, we show that the Classical algorithm of Nussinov has the highest number of cache misses followed by the algorithms Transpose (Li et al.), ByRow, ByRowSegment, and ByBox (in this order). Extensive experiments conducted on four computational platforms-Xeon E5, AMD Athlon 64 X2, Intel I7 and PowerPC A2-using two programming languages-C and Java-show that our cache efficient algorithms are also efficient in terms of run time and energy. CONCLUSION: Our benchmarking shows that, depending on the computational platform and programming language, either ByRow or ByBox give best run time and energy performance. The C version of these algorithms reduce run time by as much as 97.2% and energy consumption by as much as 88.8% relative to Classical and by as much as 56.3% and 57.8% relative to Transpose. The Java versions reduce run time by as much as 98.3% relative to Classical and by as much as 75.2% relative to Transpose. Transpose achieves run time and energy efficiency at the expense of memory as it takes twice the memory required by Classical. The memory required by ByRow, ByRowSegment, and ByBox is the same as that of Classical. As a result, using the same amount of memory, the algorithms proposed by us can solve problems up to 40% larger than those solvable by Transpose.

We consider the scheduling of flexible electric power loads so as to minimize the peak load. We settle a conjecture of Alamdari et al.[1] regarding the performance of the bottom left decreasing height heuristic to schedule preemptable loads with known power requirement and duration and having the same earliest start time and the same deadline. Specifically, we show a tight bound of 4/3 - 1/(3D) relative to the minimum peak power load, where D is the duration of the scheduling interval. On benchmark strip packing data, the bottom left decreasing height heuristic generated schedules that required up to 45% less peak power than required by schedules generated using the next fit decreasing height heuristic. On electric and plug-in hybrid electric vehicles data, these two heuristics are very competitive.

We consider the problem of data aggregation using two aggregators. We assume that the source racks can split the data they need to send to the aggregators across multiple paths. We show that obtaining a topology that minimizes aggregation time is NP-hard for k = 2, 3,4, where k the degree of ToR (top-of-rack) switches. We also show that an optimal topology can be computed in polynomial time for k = 5 and 6 and conjecture this to be the case when k > 6 as well. Experimental results show that, when k = 6, our topology optimization algorithm reduces the aggregation time by as much as 83.3% and reduces total network traffic by as much as 99.5% relative to the torus heuristic, proposed by [1].

In this paper we consider the problem of scheduling energy consumption loads in the setting of smart electric grids. Each load is characterized as a "job" by a start (arrival) time and a deadline by which a certain amount of electric energy must be delivered to the load. A job may be preemptable, i.e. it can be interrupted or non-preemptable. Specifically, we focus on scheduling a mixture of preemptable and non-preemptable jobs with the same arrival time and deadline with the goal of minimizing the peak power. We study and modify the first fit decreasing height algorithm of the strip packing problem for this purpose. We derive a performance bound for the algorithm and prove its tightness. We test the performance of the algorithm extensively on a variety of datasets including real life household data.

Pubsub is a versatile, efficient, and scalable content-based publish/subscribe system. This paper describes the architecture of Pubsub together with some of its current capabilities. A version of Pubsub optimized for event processing was benchmarked against the publish/subscribe systems BE-Tree and Siena, which also are optimized for event processing. Although the run time performance of both BE-Tree and Pubsub is orders of magnitude better than that of Siena, BE-Tree is able to handle only a restricted class of predicates while Pubsub can handle most predicate types handled by Siena. On our tests, the speedup of the fastest version of Pubsub relative to Siena ranged from a low of 18 to a high of 1,703 and averaged 185. The speedup range relative to BE-Tree was up to 9.81 and averaged 2.37. Siena’s memory requirements are about a fourth of those of BE-Tree and Pubsub. The memory required by the most memory efficient of Pubsub ’s data structures was between 4 and 16 percent less that required by BE-Tree. With respect to data structure initialization, the three systems took a comparable amount of time on some data sets while on some Pubsub could be initialized in 1/7th time required to initialize Siena and 1/14th that to initialize BE-Tree. Pubsub achieves its high performance from the use of very efficient data structures and event matching algorithms.

PC-TRIO is an indexed TCAM architecture for packet classification. In addition to index TCAMs, PC-TRIO uses wide SRAM words. On our packet classifier data sets, PC-TRIO reduced TCAM power by 96 percent and lookup time by 98 percent on an average, compared to PC-DUOS+[28]that does not use indexing or wide SRAMs. PC-DUOS+ was shown to be better than STCAM, which is a single TCAM architecture conventionally used for packet classification[28]. In this paper, we also extend PC-DUOS+ by augmenting it with wide SRAMs and index TCAMs using the same methodology as used in PC-TRIO, to obtain PC-DUOS+W. On ACL data sets, PC-DUOS+W reduced TCAM power by 86 percent and lookup time by 98 percent, compared to PC-DUOS+, which demonstrates the effectiveness of indexing and usage of wide SRAMs in reducing power and lookup time for packet classifiers.

Ensuring high data availability is a vital prerogative for Content Delivery Networks (CDN), and as we look to deploy CDN mechanisms onto mobile platforms, this imperative becomes ever more challenging. In traditional CDNs, replication ensures high availability of data, with server-loads and content-popularity often used as parameters to tightly control the process. However, the highly transient properties of such wireless and mobile devices constitute a major hurdle for any replication algorithm, rendering most simplified methods inadequate. Our contribution begins with a unique message-pulsing mechanism operating within a wireless cluster, that detects devices and ascertains their reliability. Results show the viability of our pulsing algorithm in determining a base replication level. Next, a Markovian queueing model is introduced, allowing us to induce replication based on the required speed of service. This affords finer control over the replication process, creating a more effective replication strategy suited for mobile-based CDNs. Extensive analysis of the model were performed, with parameters derived from real-world conditions. Results indicate that the model is able to compute logical values for the expected waiting times in service and thus, control the speed of replication within the CDN.

In this paper, we show that the problem of configuring the topology of a data center network to optimize data aggregation is NP-hard even when the number of aggregators is 1. Further, the approximation ratio of the algorithm proposed by Wang, Ng, and Shaikh [3] for the case of a single aggregator is (k+1)/2, where k is the degree of ToR (top-of-rack) switches and this algorithm also exhibits an anomalous behavior-increase in the switch degree may result in an increase in the aggregation time. By comparison, if topology configuration is done using the longest processing time (LPT) scheduling rule, the approximation ratio is (4/3-1/(3k)). We show that for every instance of the single aggregator topology configuration problem, the time required to aggregate using the LPT configuration is no more than that using the Wang et al. rule. By coupling the LPT rule with the rule of Wang et al., we achieve a better throughput as promised by LPT and at the same time reduce the total network traffic. Experimental results show that the LPT rule reduces aggregation time by up to 90% compared to the Wang et al. rule. The reduction in aggregation time afforded by a known improvement, COMBINE, of LPT relative to Wang et al. is up to 90.5%. More interestingly, when either of the LPT rule or COMBINE is augmented with the Wang et al. rule, total network traffic is reduced by up to 90% relative to using LPT and COMBINE with chains.

Welcome to the 19th IEEE Symposium on Computers and Communications (ISCC), which is being held on the beautiful island of Madeira, Portugal. In the past, this conference has been held in Croatia, Egypt, France, Greece, Italy, Morocco, Portugal, Spain, Tunisia, and Turkey. The 12th ISCC was held in Aveiro, Portugal in 2007, and we are excited to return to Portugal after 7 years. Madeira, known as the “Pearl of the Atlantic”, is a place with such a diversity of environments, from the sun to the mountains, from the night life to the cuisine, from the wonderful nature to the friendliness of its people, can cater to all tastes. We hope you will be able to sample some of the delights of this truly fascinating place.

This paper presents a modular, extensible, framework for rendering images from synthetic aperture radar (SAR) data on an array of heterogeneous processor architectures. Our design supports real-time reconstruction of a two-dimensional image from a matrix of echo pulses and their corresponding response values using Backprojection. Key to our design is the division of the Backprojection problem into atoms, which decomposes Backprojection along both it's input and output data dimensions, and allows scheduling algorithms to explicitly minimize communication overhead through the deliberate assignment of atoms to processors. Performance analysis on a cluster of 10 Tesla C2050 GPUs, and 5 Intel Xeon Processor X5650 CPUs has shown speedup that closely follows the number of processors in the cluster.

We consider the scheduling of flexible electric loads in a smart grid so as to minimize peak power demand. Specifically, we focus on the case when the loads are preemptable, their power requirement and duration are known in advance, and they have the same earliest start time and the same deadline. Our main results are (a) when power requests are scheduled preemptively, the peak power demand can be reduced by up to 50% relative to when these requests are scheduled non-preemptively, (b) preemptive scheduling to minimize peak power demand is NP-hard, (c) schedules with minimum peak power demand may be constructed using integer linear programming, and (d) the next-fit decreasing height heuristic may be used to quickly obtain schedules whose peak power demand is at most two times that of the optimal schedule when all jobs are preemptable and at most three times the optimal when only some jobs are preemptable. Experimental results for the integer linear program and the heuristic are also presented. Our experiments indicate a significant reduction in peak power when preemption is exploited. For example, on our data sets recharging collections of electric and plug-in hybrid vehicles without preemption required up to 26% more peak power than when this was done preemptively.

BACKGROUND: One segment of a RNA sequence might be paired with another segment of the same RNA sequence due to the force of hydrogen bonds. This two-dimensional structure is called the RNA sequence's secondary structure. Several algorithms have been proposed to predict an RNA sequence's secondary structure. These algorithms are referred to as RNA folding algorithms. RESULTS: We develop cache efficient, multicore, and GPU algorithms for RNA folding using Nussinov's algorithm. CONCLUSIONS: Our cache efficient algorithm provides a speedup between 1.6 and 3.0 relative to a naive straightforward single core code. The multicore version of the cache efficient single core algorithm provides a speedup, relative to the naive single core algorithm, between 7.5 and 14.0 on a 6 core hyperthreaded CPU. Our GPU algorithm for the NVIDIA C2050 is up to 1582 times as fast as the naive single core algorithm and between 5.1 and 11.2 times as fast as the fastest previously known GPU algorithm for Nussinov RNA folding.

We propose algorithms for distributing the classifier rules to two ternary content addressable memories (TCAMs) and for incrementally updating the TCAMs. The performance of our scheme is compared against the prevalent scheme of storing classifier rules in a single TCAM in priority order. Our scheme results in an improvement in average lookup speed by up to 49% and an improvement in update performance by up to 3.84 times in terms of the number of TCAM writes.

PUBSUB is a versatile, efficient, and scalable publish/subscribe system. This paper describes the architecture of PUBSUB together with some of its current capabilities. A version of PUBSUB optimized for event processing was benchmarked against the publish/subscribe systems BE-Tree and Siena, which also are optimized for event processing. PUBSUB processes events faster than Siena and BE-tree. On our tests, the speedup of the fastest version of PUBSUB relative to Siena was 98% on an average. The speedup range relative to BE-Tree was from 1.23 to 1.48 and averaged 1.36 on the uniform tests and PUBSUB was comparable to BE-tree on the Zipf tests. The faster times in PUBSUB were a result of very efficient data structures used in PUBSUB to store the subscriptions, and the fast matching algorithms developed to match events to subscriptions.

We develop GPU adaptations of the Aho-Corasick and multipattern Boyer-Moore string matching algorithms for the two cases GPU-to-GPU (input to the algorithms is initially in GPU memory and the output is left in GPU memory) and host-to-host (input and output are in the memory of the host CPU). For the GPU-to-GPU case, we consider several refinements to a base GPU implementation and measure the performance gain from each refinement. For the host-to-host case, we analyze two strategies to communicate between the host and the GPU and show that one is optimal with respect to runtime while the other requires less device memory. This analysis is done for GPUs with one I/O channel to the host as well as those with 2. Experiments conducted on an NVIDIA Tesla GT200 GPU that has 240 cores running off of a Xeon 2.8 GHz quad-core host CPU show that, for the GPU-to-GPU case, our Aho-Corasick GPU adaptation achieves a speedup between 8.5 and 9.5 relative to a single-thread CPU implementation and between 2.4 and 3.2 relative to the best multithreaded implementation. For the host-to-host case, the GPU AC code achieves a speedup of 3.1 relative to a single-threaded CPU implementation. However, the GPU is unable to deliver any speedup relative to the best multithreaded code running on the quad-core host. In fact, the measured speedups for the latter case ranged between 0.74 and 0.83. Early versions of our multipattern Boyer-Moore adaptations ran 7 to 10 percent slower than corresponding versions of the AC adaptations and we did not refine the multipattern Boyer-Moore codes further.

We propose an indexed TCAM architecture, PC-TRIO, for packet classifiers. PC-TRIO uses wide SRAMs and index TCAMs. On our classifier datasets, PC-TRIO on an average reduced TCAM power by 96% and lookup time by 98%, compared to PC-DUOS+ [23] that does not use indexing or wide SRAMs. We extend PC-DUOS+ by augmenting it with wide SRAMs and index TCAMs using the same methodology as used in PC-TRIO, to obtain PC-DUOS+W. On ACL datasets, PC-DUOS+W reduced TCAM power by 86% and lookup time by 98%, compared to PC-DUOS+.

We present a methodology for constructing a consistent sequence of updates to be applied incrementally to packet classifiers when the updates arrive in a cluster, where consistency is with respect to the next hop/action returned from a packet forwarding table/classifier during lookup. The sequence of updates, built using our strategy, is free from redundancies in update operations and produces a near minimal increase in table size. We prove the existence of a consistent update sequence for any given rule table and a cluster of updates. Our experiments validate our methodology and demonstrate a minimal increase in intermediate table size as a cluster of updates is applied.

Ternary Content Addressable Memory (TCAM) is a hardware device which can support high-speed table lookups and is an attractive solution for applications such as packet forwarding and classification. We investigate various TCAM architectures recently proposed for TCAM power and memory reduction in packet forwarding and show that far better power and memory performance is possible when we use an optimal prefix set for the given routing table. Compared to existing approaches, our experimental results demonstrate that our approach can significantly reduce both power (8-98 percent) and TCAM memory (45-78 percent) requirements.

We extend the fastest comparison based (sample sort) and non-comparison based (radix sort) number sorting algorithms on a GPU to sort large multifield records. Two extensions - direct (the entire record is moved whenever its key is to be moved) and indirect ((key, index) pairs are sorted using the direct extension and then records are ordered according to the obtained index permutation) are discussed. Our results show that for the By Field layout, the direct extension of the radix sort algorithm GRS[1] is the fastest for 32-bit keys when records have at least 12 fields, otherwise, the direct extension of the radix sort algorithm SRTS[14] is the fastest. For the Hybrid layout, the indirect extension of SRTS is the fastest for records with 2 or more keys.

We provide efficient single-precision and integer GPU implementations of Strassen's algorithm as well as of Winograd's variant. On an NVIDIA C1060 GPU, a speedup of 32% (35%) is obtained for Strassen's 4-level implementation and 33% (36%) for Winograd's variant relative to the sgemm (integer version of sgemm) code in CUBLAS 3.0 when multiplying 16384×16384 matrices. The maximum numerical error for the single-precision implementations is about 2 orders of magnitude higher than those for sgemm when n = 16384 and is zero for the integer implementations.

We solve workflow scheduling problems in e-Science networks, whose goal is minimizing either makespan or network resource consumption by jointly scheduling heterogeneous resources such as compute and network resources. We formulate the workflow scheduling problem incorporating multiple paths as a mixed integer linear programming (MILP) and develop several linear programming relaxation heuristics based on this formulation. Our algorithms allow dynamic multiple paths for data transfer between tasks and more flexible resource allocation that may vary over time. We evaluate our algorithms against a well-known list scheduling algorithm in e-Science networks whose size is relatively small. Our simulation results show that our heuristics are fast and work well when communication-to-computation ratios (CCRs) are small. Also, these results show that use of dynamic multiple paths and malleable resource allocation is useful for data intensive applications.

Time-domain Wavelength Interleaved Networking (TWIN) is a new optical network architecture which achieves a good balance between scheduling flexibility and deployment cost. In this paper, we solve the wavelength assignment problem for TWIN networks using topology sharing approach. We show that determining the wavelength assignment that use the minimum number of wavelengths is a NP-Complete problem. Four greedy heuristics are presented to compute the approximated solution within reasonable time. The evaluation results show that performing sorting on destination trees and wavelengths improves the assignment results, especially under low traffic loads. However, performing sorting brings some extra overheads to the sort heuristics' running time, but overall computation costs are still acceptable.

We propose algorithms for distributing the classifier rules to two TCAMs (ternary content addressable memories) and for incrementally updating the TCAMs. The performance of our scheme is compared against the prevalent scheme of storing classifier rules in a single TCAM in priority order. Our scheme results in an improvement in average lookup speed by up to 48% and our experiments demonstrate an improvement in update performance by up to 2.8 times in terms of the number of TCAM writes.

We develop GPU adaptations of the Aho-Corasick string matching algorithm for the the case when all data reside initially in the GPU memory and the results are to be left in this memory. We consider several refinements to a base GPU implementation and measure the performance gain from each refinement. Experiments conducted on an NVIDIA Tesla GT200 GPU that has 240 cores running off of a Xeon 2.8GHz quad-core host CPU show that our Aho-Corasick GPU adaptation achieves a speedup between 8.5 and 9.5 relative to a single-thread CPU implementation and between 2.4 and 3.2 relative to the best multithreaded implementation.

With its 9 cores per chip, the IBM Cell/Broadband Engine (Cell) can deliver an impressive amount of compute power and benefit the string-matching kernels of network security, networkbusiness analytics and natural language processing applications. However, the available amount of main memory on the system limits the maximum size of the dictionary supported by the string matching solution. To counter that, we propose a technique that employs compressed Aho-Corasick automata to perform fast, exact multi-pattern string matching with very large dictionaries. Our technique achieves the remarkable compression factors of 1:34 and 1:58, respectively, on the memory representation of English-language dictionaries and random binary string dictionaries. We demonstrate a parallel implementation for the Cell processor that delivers a sustained throughput between 0.90 and 2.35 Gbps per Cell blade, while supporting dictionary sizes up to 9.2 Million average patterns per Gbyte of main memory, and exhibiting resilience to content-based attacks. This high dictionary density enables natural language applications of an unprecedented scale to run on a single server blade.

No abstract available.

We develop a novel framework for supporting e-Science applications that require streaming of information between sites. Using a Synchronous Dataflow (SDF) model, our framework incorporates the communication times inherent in large scale distributed applications, and can be used to formulate the bandwidth allocation problem with throughput constraints as a multi-commodity linear programming problem. Our algorithms determine how much bandwidth is allocated to each edge while satisfying temporal constraints on collaborative tasks. Simulation results show that the bandwidth allocation by the formulated linear programming outperforms the bandwidth allocation by simple heuristics.

We propose several algorithms for topology aggregation (TA) to effectively summarize large-scale networks. These TA techniques are shown to significantly better for path requests in e-Science that may consist of simultaneous reservation of multiple paths and/or simultaneous reservation for multiple requests. Our extensive simulation demonstrates the benefits of our algorithms both in terms of accuracy and performance.

We develop a radix sort algorithm, GRS, suitable to sort multifield records on a graphics processing unit (GPU). We assume the ByField layout for records to be sorted. GRS is benchmarked against the radix sort algorithm, SDK, in NVIDIA's CUDA SDK 3.0 as well as the radix sort algorithm, SRTS, of Merrill and Grimshaw. Although SRTS is faster than both GRS and SDK when sorting numbers as well as records that have a key and an additional 32-bit field, both GRS and SDK outperform SRTS on records with 2 or more fields (in addition to the key). GRS is consistently faster than SDK on numbers as well as records with 1 or more fields. When sorting records with 9 32-bit fields, GRS is up to 74% faster than SRTS and up to 55% faster than SDK. Thus, GRS is the fastest way to radix sort records with more than 1 32-bit field on a GPU.

We consider the sorting of a large number of multifield records on the Cell Broadband engine. We show that our method, which generates runs using a 2-way merge and then merges these runs using a 4-way merge, outperforms previously proposed sort methods that use either comb sort or bitonic sort for run generation followed by a 2-way odd-even merging of runs. Interestingly, best performance is achieved by using scalar memory copy instructions rather than vector instructions.

We propose a dual TCAM architecture - DUOS, for routing tables. Four memory management schemes for TCAMs also are proposed and evaluated. DUOS and our memory management schemes support control-plane incremental updates without delaying data-plane lookups. Compared to other TCAM architectures such as CAO OPT that support incremental updates without delaying lookups, DUOS offers reduction in power consumption and improvement in average performance for update operations.

An Internet router may receive a batch of tens of thousands of updates (insert a new rule or delete/change an existing rule) in any instant (i.e., with the same time stamp). This paper deals with analyzing possible orderings of a batch of updates such that forwarding table consistency is maintained while these updates are performed one at a time as in a table that supports incremental updates rather than batch updates. This analysis results in the system CONSIST, which removes any redundancies in the batch of updates and uses a heuristic to arrange the reduced set of updates into a consistent sequence that results in near minimal increase in table size as the updates are done one by one.

We propose a method-recursive partitioning-to partition a static IP router table so that when each partition is represented using a base structure, such as a multibit trie or a hybrid shape shifting trie, there is a reduction in both the total memory required for the router table as well as in the total number of memory accesses needed to search the table. The efficacy of recursive partitioning is compared to that of the popular front-end table method to partition IP router tables. Our proposed recursive partitioning method outperformed the front-end method of all our test sets.

Ternary content-addressable memories (TCAMs) may be used to obtain a simple and very fast implementation of a router's forwarding engine. The applicability of TCAMs is, however, limited by their size and high power requirement. Zane et al. proposed a method and associated algorithms to reduce the power needed to search a forwarding table using a TCAM. We improve on both the algorithms proposed by them. Additionally, we show how to couple TCAMs and high-bandwidth SRAMs so as to overcome both the power and size limitations of a pure TCAM forwarding engine. By using one of our novel TCAM-SRAM coupling schemes (M-12 Wb), we are able to reduce TCAM memory by a factor of about 5 on IPv4 data sets and by a factor of about 2.5 on IPv6 data sets; TCAM power requirement is reduced by a factor of about 10 on IPv4 data sets and by a factor of about 6 on IPv6 data sets. These comparisons are with respect to the improved TCAM algorithms we have developed for the strategies of Zane et al. The stated improvements come at the cost of increasing SRAM requirement by a factor 2.5 for IPv4 data and a factor of 5 for IPv6 data. This cost is unimportant given that SRAMs are relatively quite cheap and have much less power requirement. For another of our novel TCAM-SRAM coupling schemes (1-12Wc), the TCAM memory and power reduced by factors of about 4 and 12 for IPv4 data sets, respectively, and by factors of about 2 and 10 for IPv6 data sets. The SRAM required, however, increased by factors of 3 and 7, respectively. These improvements come with no loss in the time (as measured by the number of TCAM searches and SRAM accesses) to do a lookup.

We present a computational geometry method for the problem of estimating the location of a source in the plane using measurements of distance-differences to it. Compared to existing solutions to this well-studied problem, this method is: (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods. This method employs a binary search on a distance-difference curve in the plane using a second distance-difference as the objective function. We show the correctness of this method by establishing the unimodality of directional derivative of the objective function within each of a small number of regions of the plane, wherein a suitable binary search is supported. The computational complexity of this method is O (log (1/ γ )), where the computed solution is guaranteed to be within a distance γ of the actual location of the source. We present simulation results to compare this method with existing DTOA localization methods.

We adapt merge sort for a single SPU of the cell broadband engine. This adaptation takes advantage of the vector instructions supported by the SPU. Experimental results indicate that our merge sort adaptation is faster than other sort algorithms (e.g., AA sort, Cell sort, quick sort) proposed for the SPU as well as faster than our SPU adaptations of shaker sort and brick sort. An added advantage is that our merge sort adaptation is a stable sort whereas none of the other sort adaptations is stable.

We develop multi-path reservation algorithms for in advance scheduling of large file transfers in connection-oriented optical networks. Specifically, to schedule a single file transfer to complete at the earliest possible time, a new max-flow based greedy algorithm (GOS) and four variants that adapt the k shortest paths and k-disjoint paths algorithms are proposed. Meanwhile, to find an earliest-finishing schedule for a batch of file transfers, a linear programming based algorithm (BATCH) is developed. Extensive experiments using both real world and random networks show that our GOS algorithm provides a good balance among maximum finish time, average finish time, and computational complexity. Although our BATCH algorithm results in the smallest maximum finish time, this algorithm has a significantly larger computational requirement than our other algorithms. GOS yields file transfer schedules with similar maximum finish time and reduces average finish time while having a significantly less computational requirement.

We investigate various TCAM architectures recently proposed for TCAM power and memory reduction and show that far better power and memory performance is possible when we use an optimal prefix set for the given routing table than when the original prefix set or the reduced prefix set as proposed in other work is used. For EaseCam, our experiments show a power and TCAM memory reduction of 96% to 98% and 62% to 69% respectively. For the suffix node architecture of, we get a power and TCAM memory reduction of 16% to 25% and 45% to 78% respectively.

We develop fast algorithms to construct space-optimal constrained 2D multibit tries for Internet packet classifier applications. Experimental evidence suggests that space-optimal 2D multibit tries and their extensions using a bucket scheme are superior to existing 2D and multidimensional packet classification schemes in terms of both memory requirement and number of memory accesses requirement. We propose a heuristic for 2D multibit tries with switch pointers, which may be used for 2D packet classification.

Ternary content-addressable memories (TCAMs) may be used to obtain a simple and very fast implementation of a router's forwarding engine. The applicability of TCAMs is, however, limited by their size and high power requirement. Zane et al. (2003) proposed a method and associated algorithms to reduce the power needed to search a forwarding table using a TCAM. We improve on both the algorithms proposed by them. Additionally, we show how to couple TCAMs and high bandwidth SRAMs so as to overcome both the power and size limitations of a pure TCAM forwarding engine.

Several routing and wavelength assignment algorithms have been developed to reserve dedicated connections for high-performance applications on optical networks. In this paper, we present an analytical and experimental evaluation of these algorithms. Our experiments indicate that the minimum-hop feasible path algorithm maximizes network utilization. We also present novel algorithms for deferred wavelength assignment that can be used for reducing the space and time requirements of many wavelength assignment algorithms.

We develop a method to compress the unoptimized Aho-Corasick automaton that is used widely in intrusion detection systems. Our method uses bitmaps with multiple levels of summaries as well as aggressive path compaction. By using multiple levels of summaries, we are able to determine a popcount with as few as 1 addition. On Snort string databases, our compressed automata take 24% to 31% less memory than taken by the compressed automata of Tuck et al. [23]. and the number of additions required to compute popcounts is reduced by about 90%.

We propose heuristics for the construction of variable-stride one-dimensional as well as fixed and variable-stride two- dimensional multibit tries. These multibit tries are suitable for the classification of Internet packets using a pipelined architecture. The variable-stride one-dimensional tries constructed by our heuristic require significantly less per-stage memory than what is required by optimal pipelined fixed-stride tries. In addition, the pipelined two-dimensional multibit tries constructed by our proposed heuristics are superior, for pipelined architectures, to two-dimensional multibit tries constructed by the best algorithms proposed for nonpipelined architectures.

We present a computational geometry method for the problem of triangulation in the plane using measurements of distance-differences. Compared to existing solutions to this well-studied problem, this method is: (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, making it suitable to low power devices, and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods. This method employs a binary search on a distance-difference curve in the plane using a second distance- difference as the objective function. We establish the unimodality of the directional derivative of the objective function within each of a small number of suitably decomposed regions of the plane to support the binary search. The computational complexity of this method is O(log21/gamma), where the computed solution is guaranteed to be within a gamma-precision region centered at the actual solution. We present simulation results to compare this method with existing DTOA triangulation methods.

We propose a method-recursive partitioning-to partition a static IP router table so that when each partition is represented using a base structure such as a multibit trie or a hybrid shape shifting trie there is a reduction in both the total memory required for the router table as well as in the total number of memory accesses needed to search the table. The efficacy of recursive partitioning is compared to that of the popular front-end table method to partition IP router tables. Our proposed recursive partitioning method outperformed the front-end method of all our test sets.

We develop algorithms for the compact representation of the 2-dimensional tries that are used for Internet packet classification. Our compact representations are experimentally compared with competing compact representations for multi-dimensional packet classifiers and found to simultaneously reduce the number of memory accesses per lookup as well as the memory required to store the classifier.

We develop an integer linear programming formulation to find the minimum cost deployment of sensors that provides the desired coverage of a target point set and propose a greedy heuristic for this problem. Our formulation permits heterogeneous multimodal sensors and is extended easily to account for nonuniform sensor detection resulting from blockages, noise, fading, and so on. A greedy algorithm for solving the proposed general ILP is developed. Additionally, isin-approximation algorithms and a polynomial- time approximation scheme are proposed for the case of grid coverage. Experiments demonstrate the superiority of our proposed algorithms over earlier algorithms for point coverage of grids by using heterogeneous sensors.

We propose a heuristic for the construction of variablestride multibit tries. These multibit tries are suitable for packet forwarding using a pipelined architecture. The variable-stride tries constructed by our heuristic require upto 1/32 of the per-stage memory required by optimal pipelined fixed-stride tries. We also develop a tree packing heuristic, which dramatically reduces the per-stage memory required by fixed- and variable-stride multibit tries constructed for pipelined architectures. On publicly available router databases, our tree packing heuristic reduces the maximum per-stage memory required by optimal pipelined fixed-stride tries

We propose heuristics for the construction of fixedand variable-stride two-dimensional multibit tries. These multibit tries are suitable for the classification of Internet packets using a pipelined architecture. The pipelined two-dimensional multibit tries constructed by our proposed heuristics are superior, for pipelined architectures, to twodimensional multibit tries constructed by the best algorithms proposed for non-pipelined architectures.

We show that two incremental power heuristics for power assignment in a wireless sensor network have approximation ratio 2. Enhancements to these heuristics are proposed. It is shown that these enhancements do not reduce the approximation ratio of the considered incremental power heuristics. However, experiments conducted by us indicate that the proposed enhancements, reduce the power cost of the assignment on average. Further, the two-edge switch enhancement yields a power-cost reduction (relative to using minimum cost spanning trees) that is, on average, twice as much as obtainable from any of the heuristics proposed earlier.

We show that the problem of routing messages in a wireless sensor network so as to maximize network lifetime is NP-hard. In our model, the online model, each message has to be routed without knowledge of future route requests. We also develop an online heuristic to maximize network lifetime. Our heuristic, which performs two shortest path computations to route each message, is superior to previously published heuristics for lifetime maximization - our heuristic results in greater lifetime and its performance is less sensitive to the selection of heuristic parameters. Additionally, our heuristic is superior on the capacity metric

We propose six new heuristics to find a source-to-destination path that satisfies two or more additive constraints on edge weights. Five of these heuristics become /spl epsi/-approximation algorithms when their parameters are appropriately set. The performance of our new heuristics is compared experimentally with that of two recently proposed heuristics for the same problem.

Summary form only given. We consider the problem of broadcasting messages in a wireless energy-limited network so as to maximize network lifetime. An O(e log e) algorithm to construct a broadcast tree that maximizes the critical energy of the network following the broadcast is developed. Additionally, we propose two new greedy heuristics to construct minimum energy broadcast trees. We show how our maximum critical energy algorithm may be coupled with our proposed greedy heuristics as well as with the greedy heuristics proposed earlier in the literature for the construction of minimum energy broadcast trees. Extensive simulations performed by us show that this coupling improves network lifetime significantly (between 48.3% and 328.9%) when compared with network lifetime using the base greedy heuristics in isolation.

We develop fast algorithms to construct space-optimal constrained two-dimensional multibit tries for Internet packet classifier applications. Experimental evidence suggests that using the same memory budget, space-optimal two-dimensional multibit tries require 1/4 to 1/3 the memory accesses required by two-dimensional one-bit tries for table lookup.

Two schemes - prefix partitioning and interval partitioning - are proposed to improve the performance of dynamic IP router-table designs. While prefix partitioning applies to all known dynamic router-table designs, interval partitioning applies to the alternative collection of binary search tree designs of Sahni and Kim [S. Sahni et al., (2004)]. Experiments using public-domain IPv4 router databases indicate that one of the proposed prefix partitioning schemes - TLDP - results in router tables that require less memory than when prefix partitioning is not used. Further significant reduction in the time to find the longest matching-prefix, insert a prefix, and delete a prefix is achieved.

We propose B-tree data structures for dynamic router-tables for the cases when the filters are prefixes as well as when they are nonintersecting ranges. A crucial difference between our data structure for prefix filters and the MRT (multiway range trees) is that, in our data structure, each prefix is stored in O(1) B-tree nodes per B-tree level, whereas, in MRT, each prefix is stored in O(m) nodes per level (m is the order of the B-tree). As a result of this difference, the measured average insert and delete times using our structure are about 30 percent less than when MRT is used. Further, an update operation of MRT will, in the worst case, make 2.5 times as many cache misses as made when our structure is used. The asymptotic complexity to find the longest matching prefix is the same and the measured time for this operation also is nearly the same for both data structures. Both B-tree structures for prefix router-tables take O(n) memory. However, our structure is more memory efficient by a constant factor. For the case of nonintersecting ranges, our data structure requires O(n log/sub m/n) memory and O(log/sub m/n) nodes are accessed during an operation (finding the highest-priority matching range, insert and delete a range).

We consider the problem of broadcasting messages in a wireless energy-limited network so as to maximize network lifetime. An O(e log e) algorithm to construct a broadcast tree that maximizes the critical energy of the network following the broadcast is developed. Additionally, we propose two new greedy heuristics to construct minimum energy broadcast trees. We show how our maximum critical energy algorithm may be coupled with our proposed greedy heuristics as well as with the greedy heuristics proposed for the construction of minimum energy broadcast trees. Extensive simulations performed by us show that this coupling improves network lifetime significantly (between 48.3 percent and 328.9 percent) when compared with network lifetime using the base greedy heuristics in isolation.

We show that determining the minimum number of resolve filters that need to be added to a set of two-dimensional (2-D) prefix filters so that the filter set can implement a given policy using the first-matching-rule-in-table tie breaker is NP-hard. Additionally, we develop a fast O(nlogn+s) time, where n is the number of filters and s is the number of conflicts, plane-sweep algorithm to detect and report all pairs of conflicting 2-D prefix filters. The space complexity of our algorithm is O(n). On our test set of 15 2-D filter sets, our algorithm runs between 4 and 17 times as fast as the 2-D trie algorithm of A. Hari et al. (2000) and uses between 1/4th and 1/8th the memory used by the algorithm of Hari et al. On the same test set, our algorithm is between 4 and 27 times as fast as the bit-vector algorithm of Baboescu and Varghese (2002) and uses between 1/205 and 1/6 as much memory. We introduce the notion of an essential resolve filter and develop an efficient algorithm to determine the essential resolve filters of a prefix filter set.

In order to provide more value-added services, the Internet needs to classify packets into flows for different treatment. This function becomes a bottleneck in the router. High performance packet classification algorithms are therefore in high demand. This paper describes a new algorithm for packet classification using the concept of independent sets. The algorithm has very small memory requirements. The search speed is not sensitive to the size of the rule table or to the percentage of wildcards in the fields. It also scales well from two-dimensional classifiers to high-dimensional ones. In particular, the algorithm is inherently parallel. Hardware tailored to this algorithm can achieve very fast search speed. The update algorithm proposed is also very fast in general.

Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, which is to find the cheapest path that satisfies certain constraints. In particular, finding the cheapest delay-constrained path is critical for real-time data flows such as voice calls. Because it is NP-complete, there has been much research into designing heuristic algorithms that solve the /spl epsiv/-approximation of the problem with an adjustable accuracy. A common approach is to discretize (i.e., scale and round) the link delay or link cost, which transforms the original problem to a simpler one solvable in polynomial time. The efficiency of the algorithms directly relates to the magnitude of the errors introduced during discretization. We propose two techniques that reduce the discretization errors, allowing faster algorithms to be designed. Reducing the overhead of the costly computation for constrained shortest paths is practically important for the design of a high-throughput QoS router, which is limited by both processing power and memory space. Our simulations show that the new algorithms reduce the execution time by an order of magnitude on power-law topologies with 1000 nodes. The reduction in memory space is similar. When there are multiple constraints, the improvement is more dramatic.

Two schemes - prefix partition and interval partition - are proposed to improve the performance of router-table design. Significant reduction in the time to find the longest matching-prefix, insert a prefix, and delete a prefix is achieved.

We propose B-tree data structures for dynamic router-tables for the cases when the filters are prefixes as well as when they are nonintersecting ranges. A crucial difference between our data structure for prefix filters and the B-tree router-table data structure of Suri et al. (2001) is that in our data structure, each prefix is stored in O(1) B-tree nodes per B-tree level, whereas in the structure of Suri et al. (2001), each prefix is stored in O(m) nodes per level (m is the order of the B-tree). As a result of this difference, a prefix may be inserted or deleted from an n-filter router table accessing only O(log/sub m/ n) nodes of our data structure; these operations access O(m log/sub m/ n) nodes using the structure of Suri et al. (2001). Eventhough the asymptotic complexity of prefix insertion and deletion is the same in both B-tree structures, experiments conducted by us show that because of the reduced cache misses for our structure, the measured average insert and delete times using our structure are about 30% less than when the B-tree structure of Suri et al. (2001) is used. Further, an update operation using the B-tree structure of Suri et al. (2001) will, in the worst case, make 2.5 times as many cache misses as made when our structure is used. The asymptotic complexity to find the longest matching prefix is the same, O(m log/sub m/ n) in both B-tree structures, and in both structures, this operation accesses O(log/sub m/ n) nodes. The measured time for this operation also is nearly the same for both data structures. Both B-tree structures for prefix router-tables take O(n) memory. However, our structure Is more memory efficient by a constant factor.

We develop a data structure called BOB (binary tree on binary tree) for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. We also develop two modified version of BOB - PBOB (prefix BOB) for the case when all rule filters are prefixes and LMPBOB (longest matching-prefix BOB) when all rule filters are prefixes and longest-prefix matching is to be done. On practical n-rule router table, BOB, PBOB and LMPBOB perform search, insert and delete In O(log n) time and with O(log n) cache misses. Experimental results also are presented.

Two versions of the Internet (IP) router-table problem are considered. In the first, the router table consists of n pairs of tuples of the form (p, a), where p is an address prefix and a is the next-hop information. In this version of the router-table problem, we are to perform the following operations: insert a new tuple, delete an existing tuple, and find the tuple with longest matching-prefix for a given destination address. We show that each of these three operations may be performed in O(log n) time in the worst case using a priority-search tree. In the second version of the router-table problem considered by us, each tuple in the table has the form (r, a), where r is a range of destination addresses matched by the tuple. The set of tuples in the table is conflict-free. For this version of the router-table problem, we develop a data structure that employs priority-search trees as well as red-black trees. This data structure permits us to perform each of the operations insert, delete, and find the tuple with most-specific matching-range for a given destination address in O(log n) time each in the worst case. The insert and delete operations preserve the conflict-free property of the set of tuples. Experimental results are also presented.

We develop an enhanced interval tree data structure that is suitable for the representation of dynamic IP router tables. Several refinements of this enhanced structure are proposed for a variety of IP router tables. For example, the data structure called BOB (binary tree on binary tree) is developed for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. When an n-rule router table is represented using BOB, the highest-priority rule that matches a destination address may be found in O(log/sup 2/n) time; a new rule may be inserted and an old one deleted in O(logn) time. For general ranges, the data structure CBOB (compact BOB) is proposed. For the case when all rule filters are prefixes, the data structure PBOB (prefix BOB) permits highest-priority matching as well as rule insertion and deletion in O(W) time, where W is the length of the longest prefix, each. When all rule filters are prefixes and longest-prefix matching is to be done, the data structure LMPBOB (longest matching-prefix BOB) permits longest-prefix matching in O(W) time; rule insertion and deletion each take O(logn) time. On practical rule tables, BOB and PBOB perform each of the three dynamic-table operations in O(logn) time and with O(logn) cache misses. The number of cache misses incurred by LMPBOB is also O(logn). Experimental results also are presented.

Internet (IP) packet forwarding is typically done by finding the longest prefix in a router table that matches the packet's destination address. For W-bit destination addresses, the use of binary tries enables us to determine the longest matching prefix in O(W) time, independent of the number n of prefixes in the router table. New prefixes may be inserted and old ones deleted in O(W) time also. Since n/spl Lt/2/sup W/ in real router tables, it is desirable to develop a data structure that permits longest prefix matching as well as the insertion and deletion of prefixes in O(logn). These three operations can be done with O(logn) cache misses using a B-tree data structure [S. Suri et al., (2001)]. However, the runtime (including operation cost and cost of cache misses) is not O(logn). In this paper, we develop a data structure in which prefix matching, prefix insertion, and deletion can each be done in O(logn) time. Experiments using real IPv4 routing databases indicate that, although the proposed data structure is slower than optimized variable-stride tries for longest prefix matching, the proposed data structure is considerably faster for the insert and delete operations.

Waldvogel et al. [ACM SIGCOMM, 1997, 25-36] have proposed a collection of hash tables (CHT) organization for an IP router table. IP lookup can be done with O(log l/sub dist/) hash-table searches, where l/sub dist/ is the number of distinct prefix-lengths (also equal to the number of hash tables in the CHT). Srinivasan and Varghese [ACM transactions on Computer Systems, Feb:1-40, 1999] have proposed the use of controlled prefix-expansion to reduce the value of l/sub dist/. The algorithm of [V. Srinivasan, 1999] does not minimize the storage required by the prefixes and markers for the resulting set of prefixes. We develop an algorithm that minimizes storage requirement but takes O(nW/sup 3/ + kW/sup 4/) time, where k is the desired number of distinct lengths, n is the number of prefixes, and W is the length of the longest prefix. Also, we propose improvements to the heuristic of [V. Srinivasan, 1999].

We consider router tables comprised of n pairs of tuples of the form (r,a), where r is a range of destination addresses matched by the tuple. The set of ranges in the table is conflict free. We develop a data structure, which employs priority-search trees as well as red-black trees, to represent the router table. This data structure permits us to perform each of the operations insert, delete, and find the tuple with most-specific matching-range for a given destination address in O(log n) each time. The insert and delete operations preserve the conflict-free property of the set of tuples. Our data structure represents the first O(log n) data structure for dynamic router tables with ranges. Experimental results are also presented.

Srinivasan and Varghese (see ACM Trans. Comput. Syst., p.1-40, 1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose dynamic programming algorithms to determine the strides of optimal multibit fixed-stride and variable-stride tries. We improve on these algorithms by providing alternative dynamic programming formulations for both fixed- and variable-stride tries. While the asymptotic complexities of our algorithms are the same as those for the corresponding algorithms of Srinivasan and Varghese, experiments using real IPv4 routing table data indicate that our algorithms run considerably faster. Our fixed-stride trie algorithm is two to four times faster on a SUN workstation and 1.5 to three times faster on a Pentium IV PC. On a SUN workstation, our variable-stride trie algorithm is between two and 17 times faster than the corresponding algorithm of Srinivasan and Varghese; on a Pentium IV PC, our algorithm is between three and 47 times faster. An added feature of our variable-stride trie algorithm is the ability to insert and delete prefixes taking a fraction of the time needed to construct an optimal variable-stride trie "from scratch".

We develop efficient algorithms for problems in computational geometry-convex hull, smallest enclosing box, ECDF two-set dominance, maximal points, all-nearest neighbor and closest-pair-on the OTIS-Mesh optoelectronic computer We also demonstrate the algorithms for computing convex hull and prefix sum with condition on a multi-dimensional mesh, which are used to compute convex hull and ECDF respectively. We show that all these problems can be solved in O(/spl radic/N) time even with N/sup 2/ inputs.

A data structure is developed that permits one to find longest matching prefixes as well as to insert and delete a prefix in O(log n) time, where n is the number of prefixes in the router table. Experimental results using a real IPv4 routing database are also presented.

This paper briefly reviews some of the more popular parallel-computer models-pipelined optical bus, optical transpose interconnect system (OTIS), and partitioned optical passive stars (POPS) network-that employ optical interconnect. The interconnect topology and some simple algorithms for each model are also described.

We develop algorithms to multiply two vectors, a vector and a matrix, and two matrices on an OTIS-Mesh optoelectronic computer. Two mappings, group row and group submesh, of a matrix onto an OTIS-Mesh are considered and the relative merits of each compared. We show that our algorithms to multiply a column and row vector use an optimal number of data moves for both the group row and group submesh mappings, our algorithm to multiply a row vector and a column vector is optimal for the group row mapping, and our algorithm to multiply a matrix by a column vector is optimal for the group row mapping.

We develop optimal or near optimal algorithms to multiply matrices and perform commonly occurring data permutations and BPC permutations on multiprocessor computers interconnected by a partitioned optical passive stars network.

We show how a multiprocessor computer interconnected by a partitioned optical passive stars network (POPS) can simulate hypercube and mesh-connected computers. POPS algorithms for data sum, prefix sum, rank, adjacent sum, consecutive sum, concentrate, distribute, and generalize are also developed. These fundamental operations form the building blocks of parallel algorithms for many applications.

We develop algorithms for histogramming, histogram modification, Hough transform, and image shrinking and expanding on an OTIS-mesh optoelectronic computer. Our algorithm for the Hough transform is based upon a mesh algorithm for the Hough transform which is also developed in this paper. This new mesh algorithm improves upon the previous mesh Hough transform algorithms.

The Optical Transpose Interconnection System (OTIS) is a recently proposed model of computing that exploits the special features of both electronic and optical technologies. In this paper we present efficient algorithms for packet routing, sorting, and selection on the OTIS-Mesh. The diameter of an N/sup 2/-processor OTIS-Mesh is 4/spl radic/N-3. We present an algorithm for routing any partial permutation in 4/spl radic/N+o(/spl radic/N) time. Our selection algorithm runs in time 6/spl radic/N+o(/spl radic/N) and our sorting algorithm runs in 8/spl radic/N+o(/spl radic/N) time. All these algorithms are randomized and the stated time bounds hold with high probability. Also, the queue size needed for these algorithms is O(1) with high probability.

In this paper, we develop algorithms for some basic operations-broadcast, window broadcast, prefix sum, data sum, rank, shift, data accumulation, consecutive sum, adjacent sum, concentrate, distribute, generalize, sorting, random access read and write-on the OTIS-Mesh model. These operations are useful in the development of efficient algorithms for numerous applications.

We develop a simple linear time algorithm to determine if a collection of two-pin nets can be routed, topologically, in a plane (i.e., single layer). Experiments indicate that this algorithm is faster than the linear time algorithm of Marek-Sadowska and Tarng. Topological routability testing of a collection of multipin nets is shown to be equivalent to planarity testing, and a simple linear time algorithm is developed for the case when the collection of modules remains connected following the deletion of all nets with more than two pins.

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. The authors show O(1) time solutions to the following computational geometry problems on the reconfigurable mesh: all-pairs nearest neighbors, convex hull, triangulation, two-dimensional maxima, two-set dominance counting, and smallest enclosing box. All these solutions accept N planar points as input and employ an N/spl times/N reconfigurable mesh. The basic scheme employed in the implementations is to recursively find an O(1) time solution. The number of recursion levels and the size of the subproblems at each level of recursion are optimized such that the problem decomposition and the solution to the problem can be obtained in constant time. As a result, they have developed some efficient merge techniques to combine the solutions for subproblems on the reconfigurable mesh. These techniques exploit reconfigurability in nontrivial ways leading to constant time solutions using optimal size of the mesh.

In this paper, we present efficient algorithms for sorting, selection, and packet routing on the AROB (Array with Reconfigurable Optical Buses) model. One of our sorting algorithms sorts n general keys in O(1) time on an AROB of size n/sup /spl epsiv///spl times/n for any constant /spl epsiv/>0. We also show that selection from out of n elements can be done in randomized O(1) time employing n processors. Our routing algorithm can route any h-relation in randomized O(h) time. All these algorithms are clearly optimal.

The author defines the master-slave multiprocessor scheduling model in which a master processor coordinates the activities of several slave processors. O(n log n) centralized, deterministic, batch-oriented algorithms are developed for some of the problems formulated. Some others are shown to be NP-hard.

Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygons in a practical VLSI mask design is small relative to the number, n, of segments or polygon edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop and implement a practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. The algorithm uses only integer operations and is, as a result, numerically stable. Experiments indicate that the algorithm will outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI/CAD problems that operate with restricted orientation geometries.

We study the problem of folding an ordered list of standard and custom cells into rows of a chip so as to minimize either the routing area or the total chip area. Nine versions of the folding problem are formulated and fast polynomial time algorithms are obtained for each. Two of our formulations correspond to problems formulated in Paik and Sahni [1993] for the folding of a stack of bit-slice components. Our algorithms for these two formulations are asymptotically superior to those of Paik and Sahni [1993].

Abstract Graphs with weights and delays associated with their edges and/or vertices are often used to model communication and signal flow networks. Network performance can be improved by upgrading the network vertices. Such an upgrade reduces the edge/vertex delays and comes at a cost. We study different formulations of this network performance improvement problem and show that these are NP‐hard. We then consider one of the formulations and develop polynomial time algorithms for some special cases and pseudopolynomial time algorithms for others.

We consider the problem of joining a row of compacted cells so as to minimize the area occupied by the cells and the interconnects. The cell joining process includes cell stretching and river routing. We propose several heuristics to join a row of cells in such a way that area is minimized. The proposed heuristics are compared, experimentally with that proposed by Cheng and Despain (1989).>

We consider two versions of the problem of folding a stack of equal width components. In both versions, when a stack is folded, a routing penalty is incurred at the fold. In one version, the height of the folded layout is given and we are to minimize width. In the other, the width of the folded layout is given and its height is to be minimized. We develop a normalization technique that permits the first version to be solved in linear time by a greedy algorithm. The second version can be solved efficiently using normalization and parametric search. Experimental results are presented.>

We show that by folding data from an n/spl times/n mesh onto an n/spl times/(n/k) submesh, sorting on the submesh, and finally unfolding back onto the entire n/spl times/n mesh it is possible to sort on bidirectional and strict unidirectional meshes using a number of routing steps that is very close to the distance lower bound for these architectures.

We develop an 0(1) time algorithm to a triangulate a set of N planar points using an NxN reconfigurable mesh with buses. Our algorithm works on all reconfigurable mesh with buses architectures.

Strings are used to represent a variety of objects such as DNA sequences, text, and numerical sequences. A model for a system for the visualization and analysis of strings was proposed by D. Mehta and S. Sahni (1992). The problem of display conflicts that arise in this model was identified and methods to overcome it were suggested. These methods require the computation of display conflicts. We present efficient algorithms to compute display conflicts.>

Examines the vertex deletion problem for weighted directed acyclic graphs (WDAGs). The objective is to delete the fewest number of vertices so that the resulting WDAG has no path of length >/spl delta/. Several simplified versions of this problem are shown to be NP-hard. However, the problem is solved in linear time when the WDAG is a rooted tree, and in quadratic time when the WDAG is a series-parallel graph.>

Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygon edges in a practical VLSI mask design is small relative to the number, n, of segments or edges. Instead, they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop a simple and practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. Experiments indicate that the algorithm will generally outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI CAD problems that operate with restricted orientation geometries.

Preplaced circuit modules may be rotated to improve performance and/or routability. It is shown that several simple versions of the module rotation problem are NP-hard.>

Three algorithms to join two compacted cells by using a combination of stretching and river routing are developed. Each of these obtains the minimum area joining. One algorithm obtains a minimum area joining that also minimizes the length of the longest wire. Another obtains a minimum area joining that has the least possible total wire length. The simplest of the algorithms guarantees only a minimum are joining. All algorithms have a low-order polynomial complexity. Experimental results indicate that the algorithms obtain joinings that are significantly superior to those obtained using the heuristic of G. Cheng and A. Despain (1989).>

A csdawg for circular strings, which is obtained by making simple modifications to the compact symmetric directed acyclic word graph (csdawg) for linear strings, is proposed. This data structure does not contain extraneous vertices and, consequently, avoids the disadvantages of previous methods. Using this method, algorithms which make use of the csdawg for linear strings can then be extended to circular strings with trivial modifications. The extended algorithms continue to have the same time and space complexities. Moreover, the extensions take the form of postprocessing or preprocessing steps which are simple to add on to a system built for linear strings, particularly in an object-oriented language.>

It is shown that the general two-layer constrained via minimization problem and the three-layer constrained via minimization problem for HVH topologies are NP-hard. A backtracking algorithm and a heuristic algorithm for the three-layer HVH constrained via minimization problem are proposed. The backtracking algorithm can also be used for three-layer non-HVH problems. Experimental results indicate that the heuristic generally outperforms that of K. Chang et al. (unpublished).>

The problem of flipping modules about their horizontal and/or vertical axes so as to minimize the estimated total wire length is considered. Polynomial time algorithms are proposed for some classes of module layouts. Further, it is shown that a simple greedy heuristic often outperforms the neural network and simulated annealing heuristics proposed earlier for this problem.>

The problem of selecting a realization for each of the blocks in a VLSI chip's floorplan so that the area of the floorplan is minimized is considered. This is done by repeatedly replacing primitive superblocks by equivalent basic blocks. A linear time algorithm to determine all the needed primitive superblocks is developed. Equivalent basic blocks are found by using L. Stockmeyer's (1983) algorithm if the primitive superblock has a slicing structure and by using branch-and-bound if not. Experimental results are provided.>

The authors consider the problem of selecting an implementation of each circuit module from a cell library so as to satisfy overall delay and area (or delay and power) requirements. Two versions of the circuit implementation problem, the basic circuit implementation problem and the general circuit implementation problem, are shown to be NP-hard. A pseudo-polynomial-time algorithm for the basic circuits is developed, and heuristics for the basic circuit implementation problem on general circuits are formulated and experimented with.>

We develop polynomial time algorithms to optimally fold stacked bit sliced architectures to minimize area subject to height or width constraints. These algorithms may also be applied to folding problems that arise in standard cell and sea-of-gates designs.>

Develops two algorithms to perform the q step shrinking and expanding of an N*N binary image on a pyramid computer with an N*N base. The time complexity of both algorithms is O( square root q). However, one uses O( square root q) space per processor, while the per-processor space requirement of the other is O(1).>

An O(n/sup 2/) time serial algorithm is developed for obtaining the medial axis transform (MAT) of an n*n image. An O(log n) time CREW PRAM algorithm and an O(log/sup 2/ n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n/sup 2/) processors. Two problems associated with the MAT, the area and perimeter reporting problem, are studied. An O(log n) time hypercube algorithm is developed for both of them, where n is the number of squares in the MAT, and the algorithms use O(n/sup 2/) processors.>

The authors introduce a novel method for the acceleration of general logic circuits based on the assumption that the delay of a circuit is its longest sensitizable (non-false) path. Hence, circuits are accelerated not by reducing path length but by making paths false. The method is based on generalizing the transformation used to obtain the bypass adder to automatically, in an area efficient way, reduce the delay of any combinational logic circuit with paths of varying length. The authors prove that a circuit realizing any function can be accelerated in this manner, give a general algorithm, and prove bounds on the size of the gain expected.>

It is shown that obtaining the optimal orientations of modules to minimize the length of the longest wire is NP-hard. If each module is permitted only two possible orientations, this can be done in linear time. When all four orientations are permissible and wires are restricted to connect modules whose separation is bounded by some constant, then the problem can also be solved in linear time.>

Squared error clustering algorithms for single-instruction multiple-data (SIMD) hypercubes are presented. The algorithms are shown to be asymptotically faster than previously known algorithms and require less memory per processing element (PE). For a clustering problem with N patterns, M features per pattern, and K clusters, the algorithms complete in O(k+log NM) steps on NM processor hypercubes. This is optimal up to a constant factor. These results are extended to the case in which NMK processors are available. Experimental results from a multiple-instruction, multiple-data (MIMD) medium-grain hypercube are also presented.>

Squared-error clustering algorithms for single-instruction multiple-data (SIMD) hypercubes are presented. These algorithms are asymptotically faster than previous algorithms and require less memory per processing element. For a clustering problem with N patterns, M features per pattern, and K clusters, the algorithms complete it in O(K+log NM) steps on NM processor hypercubes. This is optimal up to a constant factor. Experimental results from a commercially available multiple-instruction multiple-data (MIMD) medium-grain hypercube show that the clustering problem can be solved efficiently by the machines.>

The problem of constructing makespan-optimal preemptive schedules for n independent jobs on m unrelated parallel processors is discussed. For the case of two processors, we present a linear time algorithm to construct optimal schedules. The schedules generated by our algorithm have at most two preemptions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

An efficient parallel algorithm is presented for convolution on a mesh-connected computer with wraparound. The algorithm does not require a broadcast feature for data values, as assumed by previously proposed algorithms. As a result, the algorithm is applicable to both SIMD and MIMD meshes. For an N*N image and a M*M template, the previous algorithms take O(M/sup 2/q) time on an N*N mesh-connected multicomputer (q is the number of bits in each entry of the convolution matrix). The algorithms have complexity O(M/sup 2/r), where r=max (number of bits in an image entry, number of bits in a template entry). In addition to not requiring a broadcast capability, these algorithms are faster for binary images. >

A hardware accelerator for the maze routing problem is developed. This accelerator consists of three three-stage pipelines. Banked memory is used to avoid memory read/write conflicts and obtain maximum efficiency. The design is compared to other proposed designs. Unlike other proposed hardware solutions for this problem, this design does not require an increase in the number of processors as the problem size increases.>

The polynomial time algorithm obtained earlier by the authors is extended to find a minimal cardinality path set that long covers each lead or gate input of a digital logic circuit. It is shown how to find, in polynomial time, a minimal cardinality set MinMaxSP for a given combinational logic circuit. Combinational circuit verification is used to verify the sequential circuit delays.>

A polynomial-time algorithm for the pull up transistor assignment problem is developed, and it is shown that the interval selection and interval selection with pull up transistor assignment problems are NP-hard. Heuristics for these problems are proposed and compared with that proposed by C. Lursinsap and G. Gajski (ibid., vol.7, no.8, p.887-96, 1988).>

Three approximation algorithms to cover a rectilinear polygon that is neither horizontally nor vertically convex by rectangles are developed. All three guarantee covers that have at most twice as many rectangles as in an optimal cover. One takes O(n log n) time, where n is the number of vertices in the rectilinear polygon. The other two take O(n/sup 2/) and O(n/sup 4/) time. Experimental results indicate that the algorithms with complexity O(n/sup 2/) and O(n/sup 4/) often obtain optimal or near-optimal covers.>

A linear-time algorithm is developed to perform all odd (even) length circular shifts of data in an SIMD (single-instruction-stream, multiple-data-stream) hypercube. As an application, the algorithm is used to obtain an O(M/sup 2/+log N) time and O(1) memory per processor algorithm to compute the two-dimensional convolution of an N*N image and an M*M template on an N/sup 2/ processor SIMD hypercube. This improves the previous best complexity of O(M/sup 2/ log M+log N).>

Examines the via assignment problem that arises when the single-row routing approach to the interconnection problem is used. Some new complexity results and two new heuristics are obtained. Experimental results establish the superiority of the new heuristics over earlier ones.>

The notation of fair edge-deletion problems is introduced. These arise when it is desirable to control the number of edges incident to any node that are either deleted or remain following edge deletion. Six such problems were formulated for the case where the resultant graph is known to be acyclic, and the complexity of four of these is easily determined from known results. The remaining two are the authors' focus. It is shown that the problem of finding a minimum-degree deletion graph H such that G-H is acyclic is NP-hard when G is undirected, and is solvable in linear time when G is directed.>

In order to ascertain correct operation of digital logic circuits it is necessary to verify correct functional operation as well as correct operation at desired clock rates. To ascertain correct operation at desired clock rates, it is verified that signal propagation delays along a set of selected paths fall within allowed limits by applying appropriate stimuli. It has previously been suggested that an appropriate set of paths to test would be the one that includes at least one path, with maximum modeled delay, for each circuit lead or gate input. Here, algorithms to select such sets of paths with minimum cardinality are given.>

The authors develop a linear algorithm to maximize the number of terminals aligned across a routing channel. It is assumed that the terminals in the cells on either side of the channel are interchangeable. This algorithm has application to the routing of PLAs and other circuits with interchangeable terminals.>

An O(klog(k)+n) algorithm is developed, where n is the number of versions, to decompose rectilinear polygons into rectangles. This algorithm uses horizontal cuts only and reports nonoverlapping rectangles the union of which is the original rectilinear polygon. This algorithm has been programmed in Pascal on an Apollo DN320 workstation. Experimentation with rectilinear polygons from VLSI artwork indicate that the present algorithm is significantly faster than the plane sweep algorithm and the algorithm proposed by K.D. Gourley and D.M. Green (1983).>

Two subproblems that arise when routing channels with interchangeable terminals are shown to be NP-hard. These problems are: (1) determining whether there is a net-to-terminal assignment that results in an acyclic vertical and constraint graph and (2) for instances with acyclic vertical constraint graphs, obtaining net-to-terminal assignments for which the length of the longest path in the vertical constraint graph is minimum.>

A hardware accelerator for the maze routing problem is developed. This accelerator consists of three 3 stage pipelines. Banked memory is used to avoid memory read/write conflicts and obtain maximum efficiency.

Abstract We develop a linear time algorithm to determine if a given planar triangulated graph has a rectangular dual.

We develop two fast algorithms for the layering problem that arises when the single-row routing approach to wire layout is used. Both of these algorithms are for the case when the upper and lower street capacities are two. While neither of these algorithms guarantees the production of an optimal layering, it has been empirically determined that both will produce better layerings than an earlier proposed algorithm [13] for this problem. In addition, our algorithms run much faster than the earlier algorithm.

We develop a systolic design-rule checker (SDRC) for rectilinear geometries. This SDRC reports all width and spacing violations. It is expected to result in a significant speed up of the design-rule check phase of chip design.

We develop an Ο(n) algorithm to construct a rectangular dual of an n-vertex planar triangulated graph.

We develop an efficient algorithm for net extraction. This algorithm is able to efficiently handle very large layouts even when memory is limited. This is done by effectively using disk storage. The algorithm has been programmed in Fortran and is superior to other existing net extractors.

We formulate a class of adaptive heuristics for combinatorial optimization. Recently proposed methods such as simulated annealing, probabilistic hill climbing, and sequence heuristics, as well as classical perturbation methods are all members of this class of adaptive heuristics. We expose the issues involved in using an adaptive heuristic in general, and simulated annealing, probabilistic hill climbing, and sequence heuristics in particular. These issues are investigated experimentally.

We review the various VLSI architectures that have been proposed for the finite impulse response filter problem. In addition, new architectures are proposed and improved designs for some of the earlier architectures are developed.

We develop two fast algorithms for the layering problem that arises when the single row routing approach to wire layout is used. Both these algorithms are for the case when the upper and lower street capacities are two. While neither of these algorithms guarantees to produce an optimal layering, both are empirically determined to produce better layerings than an earlier proposed algorithm for this problem. In addition, our algorithms run much faster than the earlier algorithm.

The performance of simulated annealing is compared to that of other Monte Carlo methods for optimization. Our experiments show that these other methods often perform better than simulated annealing.

We develop an $O(q^2 n + n\log n)$ algorithm to obtain a preemptive schedule that minimizes maximum lateness when n jobs with given due dates and memory requirements are to be scheduled on m processors $(n \geqq m)$ of given memory sizes q is the number of distinct due dates. The value of the minimum maximum lateness can itself be found in $O(qn + n\log n)$ time.

We develop good heuristics to schedule tasks on computers that have multiple pipelines or multiple asynchronous processors. We also consider the case when different pipes or processors run at different speeds.

We develop fast linear time algorithms for single row routing when the upper and lower street capacities are less than or equal to three. A similarly fast algorithm is developed for the case when one of the streets has a capacity 1 and the other has an arbitrary capacity. Experimental results show that our algorithms are many times faster than previously developed algorithms.

This paper examines the use of binary trees in the design of efficient parallel algorithms. Using binary trees, we develop efficient algorithms for several scheduling problems. The shared memory model for parallel computation is used. Our success in using binary trees for parallel computations, indicates that the binary tree is an important and useful design tool for parallel algorithms.

The automated design of multilayer printed circuit boards is of great importance in the physical design of complex electronic systems. Wire routing is a crucial step in the design process. In this paper, the single row routing problem is considered. First, we discuss the relevance of single row routing in the context of the general routing problem. Then, we show that relaxing the restriction that backward moves are not allowed can result in smaller street congestions when there are at least four tracks in each street. Next, we obtain an O((2k)!kn log k) algorithm to determine whether or not an instance involving n nodes can be laid out (without backward moves) when only k tracks per street are available. With the additional restriction that wires are not permitted to cross streets, an efficient (O(n2)) algorithm is obtained. This restricted problem is shown to be related to a furnace assignment problem.

Efficient parallel algorithms to obtain the postfLx and tree forms of an infix arithmetic expression are developed.The shared memory model of parallel computing is used.

The single row approach represents a systematic suboptimal approach to the general multilayer rectilinear wire problem. With this approach, the single row wiring problem (i.e., one where all the points are collinear) forms the backbone of the general multilayer wiring problem. We consider the problem of generating minimum width layout for single row wiring problems. Our algorithm, which is not grid-based, is enumerative and uses a strong bounding criterion.

article Free Access Share on Parallel permutation and sorting algorithms and a new generalized connection network Authors: David Nassimi Department of Electrical Engineering and Computer Science, North-western University, Evanston, IL Department of Electrical Engineering and Computer Science, North-western University, Evanston, ILView Profile , Sartaj Sahni Department of Computer Science, 136 Lind Hall, University of Minnesota, Minneapolis, MN Department of Computer Science, 136 Lind Hall, University of Minnesota, Minneapolis, MNView Profile Authors Info & Claims Journal of the ACMVolume 29Issue 3July 1982 pp 642–667https://doi.org/10.1145/322326.322329Published:01 July 1982Publication History 174citation937DownloadsMetricsTotal Citations174Total Downloads937Last 12 Months42Last 6 weeks12 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A parallel algorithm to determine the switch settings for a Benes permutation network is developed. This algorithm can determine the switch settings for an N input/output Benes network in 0(log2N) time when a fully interconnected parallel computer with N processing elements is used. The algorithm runs in 0(N½) time on an N½× N½mesh-connected computer and 0(log4N) time on both a cube connected and a perfect shuffle computer with N processing elements. It runs in 0(k log3N) time on cube connected and perfect shuffle computers with N1+1/kprocessing elements.

In this correspondence we develop an algorithm to perform BPC permutations on a cube connected SIMD computer. The class of BPC permutations includes many of the frequently occurring permutations such as matrix transpose, vector reversal, bit shuffle, and perfect shuffle. Our algorithm is shown to be optimal in the sense that it uses the fewest possible number of unit routes to accomplish any BPC permutation.

Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two $n \times n$ matrices can be multiplied in $O(n/m + \log m)$ time when $n^2 m$, $1 \leqq m \leqq n$, processing elements (PEs) are available. When only $m^2 $, $1 \leqq m \leqq n$, PEs are available, two $n \times n$ matrices can be multiplied in $O(n^2/m + m(n/m)^{2.61} )$ time. It is shown that many graph problems can be solved efficiently using the matrix multiplication algorithms.

Considers the data broadcasting problem for single instruction stream, multiple data stream (SIMD) computers. Two versions of this problem, i.e., random access read (RAR) and random access write (RAW) are considered. Efficient data broadcasting algorithms are developed for both cases. For the case of a RAR, the complexity of the algorithm is O(q2n) on aq-dimensionalnqPE mesh-connected computer and 0(log2N) on anNPE cube-connected or perfect shuffle computer. For the case of a RAW, the complexity of the algorithm is 0(q2n+dqn) on aq-dimensional MCC and 0(log2N+dlogN) on anNPE cube-connected or perfect shuffle computer;dis the maximum number of data items written into any one PE.

A Benes permutation network capable of setting its own switches dynamically is presented. The total switch setting and delay time for the N input utput self-routing network is O(log N). It is shown that the network is capable of performing a rich class of permutations. The self-routing scheme leads to efficient O(log N) parallel algorithms to perform the same class of permutations on cube connected and perfect shuffle computers.

This paper reviews several problems that arise in the area of design automation. Most of these problems are shown to be NP-hard. Further, it is unlikely that any of these problems can be solved by fast approximation algorithms that guarantee solutions that are always within some fixed relative error of the optimal solution value. This points out the importance of heuristics and other tools to obtain algorithms that perform well on the problem instances of “interest”.

An opUmal algorithm to route data in a mesh-connected parallel computer is presented This algorithm can be used to perform any data routing that can be specified by the permutation and complementing of the bits in a PE address Matrix transpose, bit reversal, vector reversal, and perfect shuffle are examples of data permutations that can be specified in this way The algorithm presented uses the minimum number of unit distance routing steps for every data permutation that can be specified as above K~EV WORDS ANY PrmASES parallel algorithm, mesh-connected computer, ILLIAC IV, permutation, complexity, data routing CR CATEGORIES 5 25, 5 31, 6 22

An algorithm to preemptively schedule n tasks on m uniform processors is presented.It is assumed that each task is available at time 0. Associated with each task is a due time by which it is to be completed.The algorithm schedules all tasks to complete by their due times whenever possible.The asymptotic time complexity of the algorithm is O(n log n + ran).It generates O(mn) preemptions in the worst case.An example of n tasks requiring O(mn) preemptions is also presented.The algorithm can also be used when all tasks have the same due times but different release times.

Bounds are derived for the worst case performance of list schedules relative to minimum finish time schedules for uniform processor systems. The tasks to be scheduled are assumed to be independent and only nonpreemptive schedules are considered.

The computatiional complexity of several decidable problems about program schemes, recursion schemes, and simple programming languages is considered. The strong equivalence, weak equivalence, containment, halting, and divergence problems for the single variable program schemes and the linear monadic recursion schemes are shown to be $NP$-complete. The equivalence problem for the Loop 1 programming language is also shown to be $NP$-complete. Sufficient conditions for a program scheme problem to be $NP$-hard are presented. The strong equivalence problem for a subset of the single variable program schemes, the strongly free schemes, is shown to be decidable deterministically in polynomial time.

Let $G = (V,E)$ be an undirected graph in which no vertex has degree more than d. Let $|V| = n^q = 2^q $ . In this paper we present an $O(q^3 (q + d)n\log n)$ algorithm to find the connected components of G on a q-dimensional $n \times n \times \cdots \times n$ mesh-connected parallel computer. When $d = 2$, the connected components can be found in $O(q^4 n)$ time. We also show that the connected ones problem can be solved in $O(q^6 n)$ time.

An $O(m^2 n + mn\log n)$ nearly on line algorithm to preemptively schedule n independent tasks on m uniform processors is presented. It is assumed that there is a release time associated with each task. No task may be started before its release time. All tasks must be completed by a common due time (if possible). Our algorithm generates schedules having $O(nm)$ preemptions in the worst case. The algorithm can also be used to minimize maximum lateness even for the case when all jobs have the same release time but different due times.

An O(n) algorithm to sort n2elements on an Illiac IV-like n × n mesh-connected processor array is presented. This algorithm sorts the n2elements into row-major order and is an adaptation of Batcher's bitonic sort. A slight modification of our algorithm yields an O(n) algorithm to sort n2elements into snake-like row-major order. Extensions to the case of a j-dimensional processor array are discussed.

Umverstty of Mmnesota, Mtnneapohs, MmnesotaAaSTRACT An O(n) t~me algorithm is presented to obtain an opt,mal fimsh time preemptive schedule for n independent tasks on m uniform processors This algorithm assumes that the tasks are lnmally ordered by task length and that the umform processors are ordered by processor speed KEY WORDS AND PHRASES.

We study the performance of LPT (largest processing time) schedules with respect to optimal schedules in a nonpreemptive multiprocessor environment. The processors are assumed to have different speeds and the tasks being scheduled are independent.

article Free Access Share on An Efficient Algorithm for the Kolmogorov-Smirnov and Lilliefors Tests Authors: Teofilo Gonzalez Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MN Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MNView Profile , Sartaj Sahni Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MN Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MNView Profile , W. R. Franta Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MN Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MNView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 3Issue 1March 1977 pp 60–64https://doi.org/10.1145/355719.355724Published:01 March 1977Publication History 23citation2,096DownloadsMetricsTotal Citations23Total Downloads2,096Last 12 Months621Last 6 weeks49 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A linear time algorithm to obtain a minimum finish time schedule for the two-processor open shop together with a polynomial time algorithm to obtain a minimum finish time preemptive schedule for open shops with more than two processors are obtained. It is also shown that the problem of obtaining minimum finish time nonpreemptive schedules when the open shop has more than two processors is NP-complete.

Exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and weighted mean flow time on two processors. The generalization to m processors is direct. These algorithms have a worst-case complexity which is exponential in the number of tasks. Therefore approximation algorithms of low polynomial complexity are also obtained for the above problems. These algorithms are guaranteed to obtain solutions that are close to the optimal. For the case of minimizing mean flow time on m -processors an algorithm is given whose complexity is O( n log mn ).

The following job sequencing problems are studied: (i) single processor job sequencing with deadlines, (ii) job sequencing on m -identical processors to minimize finish time and related problems, (iii) job sequencing on 2-identical processors to minimize weighted mean flow time. Dynamic programming type algorithms are presented to obtain optimal solutions to these problems, and three general techniques are presented to obtain approximate solutions for optimization problems solvable in this way. The techniques are applied to the problems above to obtain polynomial time algorithms that generate “good” approximate solutions.

For P-complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete. In contrast with these results, a linear time approximation algorithm for the clustering problem is presented.

The problem of computing the determinant of a matrix of polynomials is considered.Four algorithms are compared-expansion by minors, Gausslan elimination over the integers, a method based on evaluation and interpolation, and a procedure which computes the characteristic polynomial of the matrix.Each method m analyzed with respect to its computing time and storage requirements using several models for polynomial growth.First, the asymptotic time and storage is developed for each method within each model.In addition to these asymptotm results, the analysis is done exactly for certain especially small, yet practical and important cases Then the results of empirical studies are given which support conclusions about which of the methods will work best within an actual computing environment.ca CATEGOalES" 5.14, 5.25

A serms of increasingly accurate algorithms to obtain approximate solutions to the 0/1 one-dlmensmnal knapsack problem :s presented Each algorithm guarantees a certain minimal closeness to the optimal solution value The approximate algorithms are of polynomml time complexity and reqmre only linear storage Computatmnal expermnce with these algorithms is also presented KEY WORDS ANn PHRASES knapsack problem, approximation, algomthm, efficiency CR CATEGORIES : 5.

Recent results on the computation of powers of symbolic polynomials are reviewed in perspective. Then a new algorithm is given which computes the nth power of a completely sparse polynomial using a linear number of multiplications. This is followed by experimental results comparing the new algorithm to iteration using both completely sparse and completely dense polynomials as data.

We look at several variations of the single fault detection problem for combinational logic circuits and show that deciding whether single faults are detectable by input-output (I/O) experiments is polynomially complete, i.e., there is a polynomial time algorithm to decide if these single faults are detectable if and only if there is a polynomial time algorithm for problems such as the traveling salesman problem, knapsack problem, etc.

Given r numbers s 1 , …, s r , algorithms are investigated for finding all possible combinations of these numbers which sum to M . This problem is a particular instance of the 0-1 unidimensional knapsack problem. All of the usual algorithms for this problem are investigated in terms of both asymptotic computing times and storage requirements, as well as average computing times. We develop a technique which improves all of the dynamic programming methods by a square root factor. Empirical studies indicate this new algorithm to be generally superior to all previously known algorithms. We then show how this improvement can be incorporated into the more general 0-1 knapsack problem obtaining a square root improvement in the asymptotic behavior. A new branch and search algorithm that is significantly faster than the Greenberg and Hegerich algorithm is also presented. The results of extensive empirical studies comparing these knapsack algorithms are given

We look at several problems from areas such as network flows, game theory, artificial intelligence, graph theory, integer programming and nonlinear programming and show that they are related in that any one of these problems is solvable in polynomial time if all the others are, too. At present, no polynomial time algorithm for these problems is known. These problems extend the equivalence class of problems known as P-Complete. The problem of deciding whether the class of languages accepted by polynomial time nondeterministic Turing machines is the same as that accepted by polynomial time deterministic Turing machines is related to P-Complete problems in that these two classes of languages are the same if each P-Complete problem has a polynomial deterministic solution. In view of this, it appears very likely that this equivalence class defines a class of problems that cannot be solved in deterministic polynomial time.