A halftone watermarking method of high quality, robustness, and capacity flexibility is presented in this paper. An objective halftone image quality evaluation method based on the human visual system obtained by a lea...A halftone watermarking method of high quality, robustness, and capacity flexibility is presented in this paper. An objective halftone image quality evaluation method based on the human visual system obtained by a least-mean-square algorithm is also introduced. In the encoder, the kernels-alternated error diffusion （KAEDF） is applied. It is able to maintain the computational complexity at the same level as ordinary error diffusion. Compared with Hel-Or using ordered dithering, the proposed KAEDF yields a better image quality through using error diffusion. We also propose a weighted lookup table （WLUT） in the decoder instead of lookup table （LUT）, as proposed by Pei and Guo, so as to achieve a higher decoded rate. As the experimental results demonstrate, this technique is able to guard against degradation due to tampering, cropping, rotation, and print-and-scan processes in error-diffused halftone images.展开更多
An algorithm is presented for obtaining placements of cell\|based very large scale integrated circuits, subject to timing constraints based on table\|lookup model. A new timing delay model based on some delay tables o...An algorithm is presented for obtaining placements of cell\|based very large scale integrated circuits, subject to timing constraints based on table\|lookup model. A new timing delay model based on some delay tables of fabricators is first simplified and deduced; then it is formulated as a constrained programming problem using the new timing delay model. The approach combines the well\|known quadratic placement with bottom\|up clustering, as well as the slicing partitioning strategy, which has been tested on a set of sample circuits from industry and the results obtained show that it is very promising.展开更多
This paper treats the problem of designing an optimal size for a lookup table used for sensor linearization. In small embedded systems the lookup table must be reduced to a minimum in order to reduce the memory footpr...This paper treats the problem of designing an optimal size for a lookup table used for sensor linearization. In small embedded systems the lookup table must be reduced to a minimum in order to reduce the memory footprint and intermediate table values are estimated by linear interpolation. Since interpolation introduces an estimation uncertainty that increases with the sparseness of the lookup table there is a trade-off between lookup table size and estimation precision. This work will present a theory for finding the minimum allowed size of a lookup table that does not affect the overall precision, i.e. the overall precision is determined by the lookup table entries’ precision, not by the interpolation error.展开更多
This paper proposes a power and time efficient scheme for designing IP lookup tables. The proposed scheme uses partitioned Ternary Content Addressable Memories (TCAMs) that store IP lookup tables. The proposed scheme ...This paper proposes a power and time efficient scheme for designing IP lookup tables. The proposed scheme uses partitioned Ternary Content Addressable Memories (TCAMs) that store IP lookup tables. The proposed scheme enables O(1) time penalty for updating an IP lookup table. The partitioned TCAMs allow an update done by a simple insertion without the need for routing table sorting. The organization of the routing table of the proposed scheme is based on a partition with respect to the output port for routing with a smaller priority encoder. The proposed scheme still preserves a similar storage requirement and clock rate to those of existing designs. Furthermore, this scheme reduces power consumption due to using a partitioned routing table.展开更多
PIM-SM(Protocol Independent Multicast-Sparse Mode) is a main multicast routing pro-tocol in the IPv6(Internet Protocol version 6).It can use either a shared tree or a shortest path tree to deliver data packets,consequ...PIM-SM(Protocol Independent Multicast-Sparse Mode) is a main multicast routing pro-tocol in the IPv6(Internet Protocol version 6).It can use either a shared tree or a shortest path tree to deliver data packets,consequently the multicast IP lookup engine requires,in some cases,two searches to get a correct lookup result according to its multicast forwarding rule,and it may result in a new requirement of doubling the lookup speed of the lookup engine.The ordinary method to satisfy this requirement in TCAM(Ternary Content Addressable Memory) based lookup engines is to exploit parallelism among multiple TCAMs.However,traditional parallel methods always induce more re-sources and higher design difficulty.We propose in this paper a novel approach to solve this problem.By arranging multicast forwarding table in class sequence in TCAM and making full use of the intrinsic characteristic of the TCAM,our approach can get the right lookup result with just one search and a single TCAM,while keeping the hardware of lookup engine unchanged.Experimental results have shown that the approach make it possible to satisfy forwarding IPv6 multicast packets at the full link rate of 20 Gb/s with just one TCAM with the current TCAM chip.展开更多
The well-known marching cubes method is used to generate isosurfaces from volume data or data on a 3D rectilinear grid. To do so, it refers to a lookup table to decide on the possible configurations of the isosurface ...The well-known marching cubes method is used to generate isosurfaces from volume data or data on a 3D rectilinear grid. To do so, it refers to a lookup table to decide on the possible configurations of the isosurface within a given cube, assuming we know whether each vertex lies inside or outside the surface. However, the vertex values alone do not uniquely determine how the isosurface may pass through the cube, and in particular how it cuts each face of the cube. Earlier lookup tables are deficient in various respects. The possible combinations of the different configurations of such ambiguous faces are used in this paper to find a complete and cor- rect lookup table. Isosurfaces generated using the new lookup table here are guaranteed to be watertight.展开更多
Digital design of a digital signal processor involves accurate and high-speed mathematical computation units.DSP units are one of the most power consuming and memory occupying devices.Multipliers are the common buildi...Digital design of a digital signal processor involves accurate and high-speed mathematical computation units.DSP units are one of the most power consuming and memory occupying devices.Multipliers are the common building blocks in most of the DSP units which demands low power and area constraints in the field of portable biomedical devices.This research works attempts multiple power reduction technique to limit the power dissipation of the proposed LUT multiplier unit.A lookup table-based multiplier has the advantage of almost constant area requirement’s irrespective to the increase in bit size of multiplier.Clock gating is usually used to reduce the unnecessary switching activities in idle circlet components.A clock tree structure is employed to enhance the SRAM based lookup table memory architecture.The LUT memory access operation is sequential in nature and instead of address decoder a ring counter is used to scan the memory contents and gated driver tree structure is implemented to control the clock and data switching activities.The proposed algorithm yields 20%of power reduction than existing.展开更多
DSP operation in a Biomedical related therapeutic hardware need to beperformed with high accuracy and with high speed. Portable DSP hardware’s likepulse/heart beat detectors must perform with reduced operational powe...DSP operation in a Biomedical related therapeutic hardware need to beperformed with high accuracy and with high speed. Portable DSP hardware’s likepulse/heart beat detectors must perform with reduced operational power due to lack ofconventional power sources. This work proposes a hybrid biomedical hardware chip inwhich the speed and power utilization factors are greatly improved. Multipliers are thecore operational unit of any DSP SoC. This work proposes a LUT based unsignedmultiplication which is proven to be efficient in terms of high operating speed. For n bitinput multiplication n*n memory array of 2 n bit size is required to memorize all thepossible input and output combination. Various literature works claims to be achieve highspeed multiplication with reduced LUT size by integrating a barrel shifter mechanism.This paper work address this problem, by reworking the multiplier architecture with aparallel operating pre-processing unit which used to change the multiplier and multiplicandorder with respect to the number of computational addition and subtraction stages required.Along with LUT multiplier a low power bus encoding scheme is integrated to limit the powerconstraint of the on chip DSP unit. This paper address both the speed and power optimizationtechniques and tested with various FPGA device families.展开更多
In order to classify packet, we propose a novel IP classification based the non-collision hash and jumping table trie-tree (NHJTTT) algorithm, which is based on noncollision hash Trie-tree and Lakshman and Stiliadis p...In order to classify packet, we propose a novel IP classification based the non-collision hash and jumping table trie-tree (NHJTTT) algorithm, which is based on noncollision hash Trie-tree and Lakshman and Stiliadis proposing a 2-dimensional classification algorithm (LS algorithm). The core of algorithm consists of two parts: structure the non-collision hash function, which is constructed mainly based on destination/source port and protocol type field so that the hash function can avoid space explosion problem; introduce jumping table Trie-tree based LS algorithm in order to reduce time complexity. The test results show that the classification rate of NHJTTT algorithm is up to 1 million packets per second and the maximum memory consumed is 9 MB for 10 000 rules. Key words IP classification - lookup algorithm - trie-tree - non-collision hash - jumping table CLC number TN 393.06 Foundation item: Supported by the Chongqing of Posts and Telecommunications Younger Teacher Fundation (A2003-03).Biography: SHANG Feng-jun (1972-), male, Ph.D. candidate, lecture, research direction: the smart instrument and network.展开更多
Routing technology has been forced to evolve towards higher capacity and per port packet processing speed. The ability to achieve high forwarding speed is due to either software or hardware technology. TCAM (Ternary C...Routing technology has been forced to evolve towards higher capacity and per port packet processing speed. The ability to achieve high forwarding speed is due to either software or hardware technology. TCAM (Ternary Content Addressable Memory) provides a performance advantage over other software or hardware search algorithms, often resulting in an order of magnitude reduction of search time. But slow updates may affect the performance of TCAM based routing lookup. So the key is to design a table management algorithm, which supports high speed updates in TCAMs. This paper presented three table management algorithms, and then compared their performance. Finally, the optimal one after comparing was given.展开更多
Efficient lookup is essential for peer-to-peer networks and Chord is a representative peer-to-peer lookup scheme based on distributed hash table (DHT). In peer-to-peer networks, each node maintains several unidirectio...Efficient lookup is essential for peer-to-peer networks and Chord is a representative peer-to-peer lookup scheme based on distributed hash table (DHT). In peer-to-peer networks, each node maintains several unidirectional application layer links to other nodes and forwards lookup messages through such links. This paper proposes use of bidirectional links to improve the lookup performance in Chord. Every original unidirectional link is replaced by a bidirectional link, and accordingly every node becomes an anti-finger of all its finger nodes. Both theoretical analyses and experimental results indicate that these anti-fingers can help improve the lookup performance greatly with very low overhead.展开更多
The authors present a routing lookup architecture, SDIR(SDRAM based Direct Index Routing). With pipeline and interleaving access technique, SDIR can provide scalable lookup speed from 16 7 MPPS(mega packet per second)...The authors present a routing lookup architecture, SDIR(SDRAM based Direct Index Routing). With pipeline and interleaving access technique, SDIR can provide scalable lookup speed from 16 7 MPPS(mega packet per second) to 133 MPPS with SDRAM running at 133MHz frequency.展开更多
查表匹配性能是决定软件定义网络(Software Defined Network,SDN)交换机数据转发性能的关键。随着网络规模扩大和业务负载的增加,流表规模和流表修改频率呈上升趋势,导致SDN交换机在大规模网络中的数据转发性能存在瓶颈。针对流表规模...查表匹配性能是决定软件定义网络(Software Defined Network,SDN)交换机数据转发性能的关键。随着网络规模扩大和业务负载的增加,流表规模和流表修改频率呈上升趋势,导致SDN交换机在大规模网络中的数据转发性能存在瓶颈。针对流表规模膨胀和流表频繁修改对SDN交换机查表匹配性能带来负面影响的原因进行分析,从优化SDN交换机的转发表存储结构和查表流程深入,提出一种遵循OpenFlow控制框架、基于分级表结构的转发规则优化配置机制,并通过仿真试验证明优化机制能显著提升SDN交换机转发性能。展开更多
Z-curve’s encoding and decoding algorithms are primely important in many Z-curve-based applications.The bit interleaving algorithm is the current state-of-the-art algorithm for encoding and decoding Z-curve.Although ...Z-curve’s encoding and decoding algorithms are primely important in many Z-curve-based applications.The bit interleaving algorithm is the current state-of-the-art algorithm for encoding and decoding Z-curve.Although simple,its efficiency is hindered by the step-by-step coordinate shifting and bitwise operations.To tackle this problem,we first propose the efficient encoding algorithm LTFe and the corresponding decoding algorithm LTFd,which adopt two optimization methods to boost the algorithm’s efficiency:1)we design efficient lookup tables(LT)that convert encoding and decoding operations into table-lookup operations;2)we design a bit detection mechanism that skips partial order of a coordinate or a Z-value with consecutive 0s in the front,avoiding unnecessary iterative computations.We propose order-parallel and point-parallel OpenMP-based algorithms to exploit the modern multi-core hardware.Experimental results on discrete,skewed,and real datasets indicate that our point-parallel algorithms can be up to 12.6×faster than the existing algorithms.展开更多
基金supported by National Science Council under Grants No. NSC 99-2631-H-011-001
文摘A halftone watermarking method of high quality, robustness, and capacity flexibility is presented in this paper. An objective halftone image quality evaluation method based on the human visual system obtained by a least-mean-square algorithm is also introduced. In the encoder, the kernels-alternated error diffusion （KAEDF） is applied. It is able to maintain the computational complexity at the same level as ordinary error diffusion. Compared with Hel-Or using ordered dithering, the proposed KAEDF yields a better image quality through using error diffusion. We also propose a weighted lookup table （WLUT） in the decoder instead of lookup table （LUT）, as proposed by Pei and Guo, so as to achieve a higher decoded rate. As the experimental results demonstrate, this technique is able to guard against degradation due to tampering, cropping, rotation, and print-and-scan processes in error-diffused halftone images.
基金Project Supported by National Natural Science Foundation of China!( No.697760 2 7) and by973 National Key Project( No.G1 9980)
文摘An algorithm is presented for obtaining placements of cell\|based very large scale integrated circuits, subject to timing constraints based on table\|lookup model. A new timing delay model based on some delay tables of fabricators is first simplified and deduced; then it is formulated as a constrained programming problem using the new timing delay model. The approach combines the well\|known quadratic placement with bottom\|up clustering, as well as the slicing partitioning strategy, which has been tested on a set of sample circuits from industry and the results obtained show that it is very promising.
文摘This paper treats the problem of designing an optimal size for a lookup table used for sensor linearization. In small embedded systems the lookup table must be reduced to a minimum in order to reduce the memory footprint and intermediate table values are estimated by linear interpolation. Since interpolation introduces an estimation uncertainty that increases with the sparseness of the lookup table there is a trade-off between lookup table size and estimation precision. This work will present a theory for finding the minimum allowed size of a lookup table that does not affect the overall precision, i.e. the overall precision is determined by the lookup table entries’ precision, not by the interpolation error.
文摘This paper proposes a power and time efficient scheme for designing IP lookup tables. The proposed scheme uses partitioned Ternary Content Addressable Memories (TCAMs) that store IP lookup tables. The proposed scheme enables O(1) time penalty for updating an IP lookup table. The partitioned TCAMs allow an update done by a simple insertion without the need for routing table sorting. The organization of the routing table of the proposed scheme is based on a partition with respect to the output port for routing with a smaller priority encoder. The proposed scheme still preserves a similar storage requirement and clock rate to those of existing designs. Furthermore, this scheme reduces power consumption due to using a partitioned routing table.
基金Supported by the National High-Tech Research and De-velopment Plan of China (No. 2007AA01Z2a1)the Na-tional Grand Fundamental Research 973 Program of China (No. 2007CB307102)
文摘PIM-SM(Protocol Independent Multicast-Sparse Mode) is a main multicast routing pro-tocol in the IPv6(Internet Protocol version 6).It can use either a shared tree or a shortest path tree to deliver data packets,consequently the multicast IP lookup engine requires,in some cases,two searches to get a correct lookup result according to its multicast forwarding rule,and it may result in a new requirement of doubling the lookup speed of the lookup engine.The ordinary method to satisfy this requirement in TCAM(Ternary Content Addressable Memory) based lookup engines is to exploit parallelism among multiple TCAMs.However,traditional parallel methods always induce more re-sources and higher design difficulty.We propose in this paper a novel approach to solve this problem.By arranging multicast forwarding table in class sequence in TCAM and making full use of the intrinsic characteristic of the TCAM,our approach can get the right lookup result with just one search and a single TCAM,while keeping the hardware of lookup engine unchanged.Experimental results have shown that the approach make it possible to satisfy forwarding IPv6 multicast packets at the full link rate of 20 Gb/s with just one TCAM with the current TCAM chip.
文摘The well-known marching cubes method is used to generate isosurfaces from volume data or data on a 3D rectilinear grid. To do so, it refers to a lookup table to decide on the possible configurations of the isosurface within a given cube, assuming we know whether each vertex lies inside or outside the surface. However, the vertex values alone do not uniquely determine how the isosurface may pass through the cube, and in particular how it cuts each face of the cube. Earlier lookup tables are deficient in various respects. The possible combinations of the different configurations of such ambiguous faces are used in this paper to find a complete and cor- rect lookup table. Isosurfaces generated using the new lookup table here are guaranteed to be watertight.
文摘Digital design of a digital signal processor involves accurate and high-speed mathematical computation units.DSP units are one of the most power consuming and memory occupying devices.Multipliers are the common building blocks in most of the DSP units which demands low power and area constraints in the field of portable biomedical devices.This research works attempts multiple power reduction technique to limit the power dissipation of the proposed LUT multiplier unit.A lookup table-based multiplier has the advantage of almost constant area requirement’s irrespective to the increase in bit size of multiplier.Clock gating is usually used to reduce the unnecessary switching activities in idle circlet components.A clock tree structure is employed to enhance the SRAM based lookup table memory architecture.The LUT memory access operation is sequential in nature and instead of address decoder a ring counter is used to scan the memory contents and gated driver tree structure is implemented to control the clock and data switching activities.The proposed algorithm yields 20%of power reduction than existing.
文摘DSP operation in a Biomedical related therapeutic hardware need to beperformed with high accuracy and with high speed. Portable DSP hardware’s likepulse/heart beat detectors must perform with reduced operational power due to lack ofconventional power sources. This work proposes a hybrid biomedical hardware chip inwhich the speed and power utilization factors are greatly improved. Multipliers are thecore operational unit of any DSP SoC. This work proposes a LUT based unsignedmultiplication which is proven to be efficient in terms of high operating speed. For n bitinput multiplication n*n memory array of 2 n bit size is required to memorize all thepossible input and output combination. Various literature works claims to be achieve highspeed multiplication with reduced LUT size by integrating a barrel shifter mechanism.This paper work address this problem, by reworking the multiplier architecture with aparallel operating pre-processing unit which used to change the multiplier and multiplicandorder with respect to the number of computational addition and subtraction stages required.Along with LUT multiplier a low power bus encoding scheme is integrated to limit the powerconstraint of the on chip DSP unit. This paper address both the speed and power optimizationtechniques and tested with various FPGA device families.
文摘In order to classify packet, we propose a novel IP classification based the non-collision hash and jumping table trie-tree (NHJTTT) algorithm, which is based on noncollision hash Trie-tree and Lakshman and Stiliadis proposing a 2-dimensional classification algorithm (LS algorithm). The core of algorithm consists of two parts: structure the non-collision hash function, which is constructed mainly based on destination/source port and protocol type field so that the hash function can avoid space explosion problem; introduce jumping table Trie-tree based LS algorithm in order to reduce time complexity. The test results show that the classification rate of NHJTTT algorithm is up to 1 million packets per second and the maximum memory consumed is 9 MB for 10 000 rules. Key words IP classification - lookup algorithm - trie-tree - non-collision hash - jumping table CLC number TN 393.06 Foundation item: Supported by the Chongqing of Posts and Telecommunications Younger Teacher Fundation (A2003-03).Biography: SHANG Feng-jun (1972-), male, Ph.D. candidate, lecture, research direction: the smart instrument and network.
文摘Routing technology has been forced to evolve towards higher capacity and per port packet processing speed. The ability to achieve high forwarding speed is due to either software or hardware technology. TCAM (Ternary Content Addressable Memory) provides a performance advantage over other software or hardware search algorithms, often resulting in an order of magnitude reduction of search time. But slow updates may affect the performance of TCAM based routing lookup. So the key is to design a table management algorithm, which supports high speed updates in TCAMs. This paper presented three table management algorithms, and then compared their performance. Finally, the optimal one after comparing was given.
文摘Efficient lookup is essential for peer-to-peer networks and Chord is a representative peer-to-peer lookup scheme based on distributed hash table (DHT). In peer-to-peer networks, each node maintains several unidirectional application layer links to other nodes and forwards lookup messages through such links. This paper proposes use of bidirectional links to improve the lookup performance in Chord. Every original unidirectional link is replaced by a bidirectional link, and accordingly every node becomes an anti-finger of all its finger nodes. Both theoretical analyses and experimental results indicate that these anti-fingers can help improve the lookup performance greatly with very low overhead.
文摘The authors present a routing lookup architecture, SDIR(SDRAM based Direct Index Routing). With pipeline and interleaving access technique, SDIR can provide scalable lookup speed from 16 7 MPPS(mega packet per second) to 133 MPPS with SDRAM running at 133MHz frequency.
文摘查表匹配性能是决定软件定义网络(Software Defined Network,SDN)交换机数据转发性能的关键。随着网络规模扩大和业务负载的增加,流表规模和流表修改频率呈上升趋势,导致SDN交换机在大规模网络中的数据转发性能存在瓶颈。针对流表规模膨胀和流表频繁修改对SDN交换机查表匹配性能带来负面影响的原因进行分析,从优化SDN交换机的转发表存储结构和查表流程深入,提出一种遵循OpenFlow控制框架、基于分级表结构的转发规则优化配置机制,并通过仿真试验证明优化机制能显著提升SDN交换机转发性能。
基金funded by the Key Project of the Open Fund for Computer Technology Applications in Yunnan under Grant no.CB23031D025A.
文摘Z-curve’s encoding and decoding algorithms are primely important in many Z-curve-based applications.The bit interleaving algorithm is the current state-of-the-art algorithm for encoding and decoding Z-curve.Although simple,its efficiency is hindered by the step-by-step coordinate shifting and bitwise operations.To tackle this problem,we first propose the efficient encoding algorithm LTFe and the corresponding decoding algorithm LTFd,which adopt two optimization methods to boost the algorithm’s efficiency:1)we design efficient lookup tables(LT)that convert encoding and decoding operations into table-lookup operations;2)we design a bit detection mechanism that skips partial order of a coordinate or a Z-value with consecutive 0s in the front,avoiding unnecessary iterative computations.We propose order-parallel and point-parallel OpenMP-based algorithms to exploit the modern multi-core hardware.Experimental results on discrete,skewed,and real datasets indicate that our point-parallel algorithms can be up to 12.6×faster than the existing algorithms.
