16600200
Studying Software Implementations of Elliptic Curve Cryptography
Elliptic curve cryptography (ECC) provides a similar level of security to conventional integer-based public-key algorithms, but with much shorter keys. ECC over binary field is of special interest because the operations in binary field are thought more space and time efficient. However, the software implementations of ECC over binary field are still slow, especially on low-end processors that are used in small computing devices such as sensor nodes. In this paper, we study the software implementations of ECC on processors with different word sizes. With a set of algorithms that we identified, we can perform 163-bit ECC in 13.9 seconds on an 8-bit processor at a clock rate of 8 MHz
2847085
Refining instruction set architecture for high-performance multimedia processing in constrained environments
Multimedia processing in software has been significantly accelerated by the addition of subword-parallel instructions to the instruction set architectures (ISAs) of modem microprocessors. While some of these multimedia instructions are simple and effective, others are very complex, requiring large, special-purpose functional units that are not practical for constrained environments such as handheld multimedia information appliances. For such environments, low-power and low-cost are as important as the high performance required for real-time multimedia processing and the general-purpose programmability required to support an ever growing range of applications. In this paper, we introduce PLX, a concise ISA that selects the most useful features from the first two generations of multimedia instructions added to microprocessors, and explores new ISA features for high-performance yet low-cost multimedia processing with small footprint processors. PLX is unique in that it is designed from scratch as a fully subword-parallel architecture with novel features like datapath scalability from 32-bit to 128-bit words, and a new definition of predication for reducing conditional branches. We illustrate the use of PLX's architectural features with four frequently used multimedia kernels: discrete cosine transform, pixel padding, clip test and median filter. Our performance results show that a 64-bit PLX implementation achieves significant speedups compared to a basic 64-bit RISC processor and to IA-32 processors with MMX and SSE multimedia extensions. PLX's datapath scalability feature often provides an additional 2x speedup in a cost-effective way.
18490417
Subword sorting with versatile permutation instructions
Subword parallelism has succeeded in accelerating many multimedia applications. Subword permutation instructions have been proposed to efficiently rearrange subwords in or among registers. Bit-level permutation instructions have also been proposed recently for their importance in cryptography. However, important algorithms, especially those with many conditional control dependencies such as sorting, have not exploited the advantage of subword parallel instructions. In this paper, we show how one of the bit permutation instructions, GRP, can be used for fast sorting. In the process, we demonstrate the versatility of this permutation instruction for uses other than bit permutations. This versatility is important in considering the addition of a new instruction to a general-purpose processor. The results show that our sorting methods have a significant speedup even when compared with the fastest sorting algorithms. We also discuss the hardware implementation of the GRP instruction and compare its latency to a typical processor's cycle time.
14970039
Enlisting Hardware Architecture to Thwart Malicious Code Injection
Software vulnerabilities that enable the injection and execution of malicious code in pervasive Internet-connected computing devices pose serious threats to cyber security. In a common type of attack, a hostile party induces a software buffer overflow in a susceptible computing device in order to corrupt a procedure return address and transfer control to malicious code. These buffer overflow attacks are often employed to recruit oblivious hosts into distributed denial of service (DDoS) attack networks, which ultimately launch devastating DDoS attacks against victim networks or machines. In spite of existing software countermeasures that seek to prevent buffer overflow exploits, many systems remain vulnerable.
13469693
Validating Word-Oriented Processors for Bit and Multi-word Operations
We examine secure computing paradigms to identify any new architectural challenges for future general-purpose processors. Some essential security functions can be provided by different classes of cryptography algorithms. We identify two categories of operations in these algorithms that are not common in previous general-purpose workloads: bit operations within a word and multi-word operations. Both challenge the basic word orientation of processors. We show how very complex bit-level operations, namely arbitrary bit permutations within a word, can be achieved in O(1) cycles, rather than O(n) cycles as in existing RISC processors. We describe two solutions: one using only microarchitecture changes, and another with Instruction Set Architecture (ISA) support. We generalize our solutions to define datarich execution with MOMR (Multi-word Operands Multi-word Result) functional units. This can address both challenges, leveraging available resources in typical processors with minimal additional cost. Thus we validate the basic word-orientation of processor architectures, since they can also provide superior performance for both bit and multi-word operations needed by cryptographic processing.
8693957
Single-Cycle Bit Permutations with MOMR Execution
Secure computing paradigms impose new architectural challenges for general-purpose processors. Cryptographic processing is needed for secure communications, storage, and computations. We identify two categories of operations in symmetric-key and public-key cryptographic algorithms that are not common in previous general-purpose workloads: advanced bit operations within a word and multi-word operations. We define MOMR (Multiple Operands Multiple Results) execution or datarich execution as a unified solution to both challenges. It allows arbitrary n-bit permutations to be achieved in one or two cycles, rather than O(n) cycles as in existing RISC processors. It also enables significant acceleration of multi-word multiplications needed by public-key ciphers. We propose two implementations of MOMR: one employs only hardware changes while the other uses Instruction Set Architecture (ISA) support. We show that MOMR execution leverages available resources in typical multi-issue processors with minimal additional cost. Multi-issue processors enhanced with MOMR units provide additional speedup over standard multi-issue processors with the same datapath. MOMR is a general architectural solution for word-oriented processor architectures to incorporate datarich operations.
19898332
An algorithm for partial Grundy number on trees
A coloring of a graph G=(V,E) is a partition {V"1,V"2,...,V"k} of V into independent sets or color classes. A vertex [email protected]?V"i is a Grundy vertex if it is adjacent to at least one vertex in each color class V"j for every j
18028792
Semantics Supervised Cluster-Based Index for Video Databases
High-dimensional index is one of the most challenging tasks for content-based video retrieval (CBVR). Typically, in video database, there exist two kinds of clues for query: visual features and semantic classes. In this paper, we modeled the relationship between semantic classes and visual feature distributions of data set with the Gaussian mixture model (GMM), and proposed a semantics supervised cluster based index approach (briefly as SSCI) to integrate the advantages of both semantic classes and visual features. The entire data set is divided hierarchically by a modified clustering technique into many clusters until the objects within a cluster are not only close in the visual feature space but also within the same semantic class, and then an index entry including semantic clue and visual feature clue is built for each cluster. Especially, the visual feature vectors in a cluster are organized adjacently in disk. So the SSCI-based nearest-neighbor (NN) search can be divided into two phases: the first phase computes the distances between the query example and each cluster index and returns the clusters with the smallest distance, here namely candidate clusters; then the second phase retrieves the original feature vectors within the candidate clusters to gain the approximate nearest neighbors. Our experiments showed that for approximate searching the SSCI-based approach was faster than VA+-based approach; moreover, the quality of the result set was better than that of the sequential search in terms of semantics.
14958987
Question Answering Summarization of Multiple Biomedical Documents
In this paper we introduce a system that automatically summarizes multiple biomedical documents relevant to a question. The system extracts biomedical and general concepts by utilizing concept-level knowledge from domain-specific and domain-independent sources. Semantic role labeling, semantic subgraph-based sentence selection and automatic post-editing are involved in the process of finding the information need. Due to the absence of expert-written summaries of biomedical documents, we propose an approximate evaluation by taking MEDLINE abstracts as expert-written summaries. Evaluation results indicate that our system does help in answering questions and the automatically generated summaries are comparable to abstracts of biomedical articles, as evaluated using the ROUGE measure.
18050486
Perspectives on cognitive informatics
From a scientific perspective explaining how the brain thinks is a big goal. Cognitive informatics studies intelligent behavior from a computational point of view in terms of updated research efforts and processes of brain science and neuroscience. Cognitive informatics is the interdisciplinary study of cognition. Cognition includes mental states and processes, such as thinking, reasoning, remembering, language understanding and generation, visual and auditory perception, learning, consciousness, emotions, etc. In this paper we will point out basic research topics of learning, memory, thought, language, and neural computing which are active fields related to cognitive informatics.
5848156
Swarm Intelligence Clustering Algorithm Based on Attractor
Ant colonies behavior and their self-organizing capabilities have been popularly studied, and various swarm intelligence models and clustering algorithms also have been proposed. Unfortunately, the cluster number is often too high and convergence is also slow. We put forward a novel structure-attractor, which actively attracts and guides the ant's behavior, and implement an efficient strategy to adaptively control the clustering behavior. Our experiments show that swarm intelligence clustering algorithm based on attractor (SICABA for short) greatly improves the convergence speed and clustering quality compared with LF and also has many notable virtues such as flexibility, decentralization compared with conventional algorithms.