14 results
Search Results
2. Two versions of architectures for dynamic implied addressing mode
- Author
-
Youn, Jonghee M., Ahn, Minwook, Paek, Yunheung, Kim, Jongwung, and Cho, Jeonghun
- Subjects
Algorithm ,Electrical engineering ,Mathematical optimization ,Algorithms ,Computer science ,Electrical engineering - Abstract
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2010.05.014 Byline: Jonghee M. Youn (a), Minwook Ahn (a), Yunheung Paek (a), Jongwung Kim (b), Jeonghun Cho (b) Keywords: Embedded processor; Compiler; Optimization; Addressing mode Abstract: The complexity of today's embedded applications increases with various requirements such as execution time, code size or power consumption. To satisfy these requirements for performance, efficient instruction set design is one of the important issues because an instruction customized for specific applications can make better performance than multiple instructions in aspect of fast execution time, decrease of code size, and low power consumption. Limited encoding space, however, does not allow adding application specific and complex instructions freely to the instruction set architecture. To resolve this problem, conventional architectures increases free space for encoding by trimming excessive bits required beyond the fixed word length. This approach however shows severe weakness in terms of the complexity of compiler, code size and execution time. In this paper, we propose a new instruction encoding scheme based on the dynamic implied addressing mode (DIAM) to resolve limited encoding space and side-effect by trimming. We report our two versions of architectures to support our DIAM-based approach. In the first version, we use a special on-chip memory to store extra encoding information. In the second version, we replace the memory by a small on-chip buffer along with a special instruction. We also suggest a code generation algorithm to fully utilize DIAM. In our experiment, the architecture augmented with DIAM shows about 8% code size reduction and 18% speed up on average, as compared to the basic architecture without DIAM. Author Affiliation: (a) School of Electrical Engineering and Computer Science, Seoul National University, Republic of Korea (b) School of Electrical Engineering and Computer Science, Kyungpook National University, Republic of Korea Article History: Received 1 October 2009; Revised 14 May 2010; Accepted 31 May 2010 Article Note: (footnote) [star] This is a revised and expanded version of two papers published in the 7th IEEE Symposium on Application Specific Processors, July 2009 and the 11th IEEE International Conference on High Performance Computing and Communications, June 2009 .
- Published
- 2010
3. A Fast Algorithm to Find All-Pairs Shortest Paths in Complex Networks.
- Author
-
Peng, Wei, Hu, Xiaofeng, Zhao, Feng, and Su, Jinshu
- Subjects
ALGORITHMS ,PATHS & cycles in graph theory ,GRAPH theory ,COMPUTER science ,ROUTING (Computer network management) ,APPROXIMATION theory ,MATHEMATICAL optimization - Abstract
Abstract: Finding shortest paths is a fundamental problem in graph theory, which has a large amount of applications in many areas like computer science, operations research, network routing and network analysis. Although many exact and approximate algorithms have been proposed, it is still a time-consuming task to calculate shortest paths for large-scale networks with tremendous volume of data available in recent years. In this paper, we find that the classic Dijkstra''s algorithm can be improved by simple modification. We propose a fast algorithm which utilize the preiously-calculated results to accelerate the latter calculation. Simple optimization strategies are also proposed with consideration of characteristics of scale-free complex networks. Our experimental results show that the average running time of our algorithm is lower than the Dijkstra''s algorithm by a factor relating to the connection probability in random networks of ER model. The performance of our algorithm is significantly better than the Dijkstra''s algorithm in scale-free networks generated by the AB model. The results show that the time complexity is reduced to about O(n
2.4 ) in scalefree complex networks. When the optimization strategies are applied, the algorithm performance is further improved slightly in scale-free networks. [Copyright &y& Elsevier]- Published
- 2012
- Full Text
- View/download PDF
4. An extended one-versus-rest support vector machine for multi-label classification
- Author
-
Xu, Jianhua
- Subjects
- *
SUPPORT vector machines , *LEARNING classifier systems , *MACHINE learning , *ALGORITHMS , *COMPUTER science , *QUADRATIC programming , *MATHEMATICAL optimization , *MATHEMATICAL analysis - Abstract
Abstract: Hybrid strategy, which generalizes a specific single-label algorithm while one or two data decomposition tricks are applied implicitly or explicitly, has become an effective and efficient tool to design and implement various multi-label classification algorithms. In this paper, we extend traditional binary support vector machine by introducing an approximate ranking loss as its empirical loss term to build a novel support vector machine for multi-label classification, resulting into a quadratic programming problem with different upper bounds of variables to characterize label correlation of individual instance. Further, our optimization problem can be solved via combining one-versus-rest data decomposition trick with modified binary support vector machine, which dramatically reduces computational cost. Experimental study on ten multi-label data sets illustrates that our method is a powerful candidate for multi-label classification, compared with four state-of-the-art multi-label classification approaches. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
5. High-dimensional objective optimizer: An evolutionary algorithm and its nonlinear analysis
- Author
-
Huang, Jun, Huang, Xiaohong, Ma, Yan, and Liu, Yanbing
- Subjects
- *
MATHEMATICAL optimization , *ARTIFICIAL intelligence , *NONLINEAR statistical models , *MARTINGALES (Mathematics) , *STOCHASTIC convergence , *MATHEMATICAL analysis , *ALGORITHMS , *COMPUTER science - Abstract
Abstract: Last few years have witnessed the development of various multi-objective evolutionary algorithms since they allow the generation of the overall Pareto front for multi-objective optimizations. With the problems in the real-world becoming more and more complex, however, no reported work in the literature focuses on the high-dimensional objective optimizations (HOPs). In this paper, we propose an evolutionary algorithm named HOEA (high-dimensional objective evolutionary algorithm) for HOPs. By adopting the concept of nonlinear definition for optimizing object, HOPs can be solved by HOEA, while the well-known multi-objective evolutionary algorithms work poorly on HOPs. We further analyze the nonlinear dynamic properties of HOEA on the basis of martingale theoretical framework. The theoretical results indicate that this new algorithm is indeed capable of achieving convergence. We also conduct experiments on HOEA with two representative test instances. The experimental results either confirm our theoretical results or show that the proposed algorithm is efficient and effective for HOPs. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
6. An improved algorithm for support vector clustering based on maximum entropy principle and kernel matrix
- Author
-
Guo, Chonghui and Li, Fang
- Subjects
- *
SUPPORT vector machines , *ALGORITHMS , *CLUSTER analysis (Statistics) , *MAXIMUM entropy method , *LINEAR algebra , *MATHEMATICAL optimization , *NUMERICAL analysis , *COMPUTER science - Abstract
Abstract: The support vector clustering (SVC) algorithm consists of two main phases: SVC training and cluster assignment. The former requires calculating Lagrange multipliers and the latter requires calculating adjacency matrix, which may cause a high computational burden for cluster analysis. To overcome these difficulties, in this paper, we present an improved SVC algorithm. In SVC training phase, an entropy-based algorithm for the problem of calculating Lagrange multipliers is proposed by means of Lagrangian duality and the Jaynes’ maximum entropy principle, which evidently reduces the time of calculating Lagrange multipliers. In cluster assignment phase, the kernel matrix is used to preliminarily classify the data points before calculating adjacency matrix, which effectively reduces the computing scale of adjacency matrix. As a result, a lot of computational savings can be achieved in the improved algorithm by exploiting the special structure in SVC problem. Validity and performance of the proposed algorithm are demonstrated by numerical experiments. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
7. Differential evolution and quantum-inquired differential evolution for evolving Takagi–Sugeno fuzzy models
- Author
-
Su, Haijun and Yang, Yupu
- Subjects
- *
FUZZY systems , *MATHEMATICAL optimization , *NUMERICAL analysis , *COMPUTER science , *AUTOMATIC identification , *ALGORITHMS , *ENCODING , *PERFORMANCE - Abstract
Abstract: The differential evolution (DE) is a global optimization algorithm to solve numerical optimization problems. Recently the quantum-inquired differential evolution (QDE) has been proposed for binary optimization. This paper proposes DE/QDE to learn the Takagi–Sugeno (T–S) fuzzy model. DE/QDE can simultaneously optimize the structure and the parameters of the model. Moreover a new encoding scheme is given to allow DE/QDE to be easily performed. The two benchmark problems are used to validate the performance of DE/QDE. Compared to some existing methods, DE/QDE shows the competitive performance in terms of accuracy. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
8. Optimization for first order Delaunay triangulations
- Author
-
van Kreveld, Marc, Löffler, Maarten, and Silveira, Rodrigo I.
- Subjects
- *
TRIANGULATION , *COMPUTER science , *ALGORITHMS , *POLYHEDRAL functions , *MATHEMATICAL optimization , *APPROXIMATION theory - Abstract
Abstract: This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles instead of only to single triangles. We give efficient algorithms to optimize certain measures, including measures related to the area ratio of adjacent triangles, angle between outward normals of adjacent triangles (for polyhedral terrains), and number of convex vertices. Some other measures are shown to be NP-hard. These include maximum vertex degree, number of convex edges, and number of mixed vertices. For the latter two measures we provide, for any constant , factor approximation algorithms that run in and time (when the Delaunay triangulation is given). For minimizing the maximum vertex degree, the NP-hardness proof provides an inapproximability result. Our results are presented for the class of first order Delaunay triangulations, but also apply to triangulations where for every triangle at least two edges are fixed. The approximation result on maximizing the number of convex edges is also extended to k-th order Delaunay triangulations. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
9. Efficiently computing succinct trade-off curves
- Author
-
Vassilvitskii, Sergei and Yannakakis, Mihalis
- Subjects
- *
MATHEMATICAL optimization , *ALGORITHMS , *COMBINATORIAL optimization , *COMPUTER science - Abstract
Abstract: Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in Papadimitriou and Yannakakis [On the approximability of trade-offs and optimal access of web sources, in: Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000] that there exist polynomial size approximations for any , and that under certain general conditions, such approximate -Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an -Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax to any , then we can efficiently construct an -curve that uses no more points than the smallest -curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger value. We present an algorithm that is 4-competitive for any . We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax by an arbitrary constant. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
10. Ockham’s Razor in memetic computing: Three stage optimal memetic exploration
- Author
-
Iacca, Giovanni, Neri, Ferrante, Mininno, Ernesto, Ong, Yew-Soon, and Lim, Meng-Hiot
- Subjects
- *
PARSIMONIOUS models , *ALGORITHMS , *COMPUTER science , *COMPLEXITY (Philosophy) , *ARTIFICIAL intelligence , *MATHEMATICAL optimization , *STOCHASTIC processes , *DIGITAL signal processing - Abstract
Abstract: Memetic computing is a subject in computer science which considers complex structures as the combination of simple agents, memes, whose evolutionary interactions lead to intelligent structures capable of problem-solving. This paper focuses on memetic computing optimization algorithms and proposes a counter-tendency approach for algorithmic design. Research in the field tends to go in the direction of improving existing algorithms by combining different methods or through the formulation of more complicated structures. Contrary to this trend, we instead focus on simplicity, proposing a structurally simple algorithm with emphasis on processing only one solution at a time. The proposed algorithm, namely three stage optimal memetic exploration, is composed of three memes; the first stochastic and with a long search radius, the second stochastic and with a moderate search radius and the third deterministic and with a short search radius. The bottom-up combination of the three operators by means of a natural trial and error logic, generates a robust and efficient optimizer, capable of competing with modern complex and computationally expensive algorithms. This is suggestive of the fact that complexity in algorithmic structures can be unnecessary, if not detrimental, and that simple bottom-up approaches are likely to be competitive is here invoked as an extension to memetic computing basing on the philosophical concept of Ockham’s Razor. An extensive experimental setup on various test problems and one digital signal processing application is presented. Numerical results show that the proposed approach, despite its simplicity and low computational cost displays a very good performance on several problems, and is competitive with sophisticated algorithms representing the-state-of-the-art in computational intelligence optimization. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
11. Boundary-based lower-bound functions for dynamic time warping and their indexing
- Author
-
Zhou, Mi and Wong, Man Hon
- Subjects
- *
ALGORITHMS , *TIME series analysis , *NEAREST neighbor analysis (Statistics) , *METRIC spaces , *COMPUTER science , *INFORMATION science , *MATHEMATICAL optimization , *SPATIAL analysis (Statistics) - Abstract
Abstract: Dynamic time warping (DTW) is a powerful technique in the time-series similarity search. However, its performance on large-scale data is unsatisfactory because of its high computational cost and the fact that it cannot be indexed directly. The lower bound technique for DTW is an effective solution to this problem. In this paper, we explain the existing lower-bound functions from a unified perspective and show that they are only special cases under our framework. We then propose a group of lower-bound functions for DTW and compare their performances through extensive experiments. The experimental results show that the new methods are better than the existing ones in most cases, and a theoretical explanation of the results is also given. We further implement an index structure based on the new lower-bound function. Experimental results demonstrate a similar conclusion. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
12. Dynamic multi-objective optimization based on membrane computing for control of time-varying unstable plants
- Author
-
Huang, Liang, Suh, Il Hong, and Abraham, Ajith
- Subjects
- *
INVARIANTS (Mathematics) , *MATHEMATICAL optimization , *COMPUTER science , *DECISION making , *BIOLOGICALLY inspired computing , *ALGORITHMS , *EXPERIMENTS - Abstract
Abstract: Dynamic multi-objective optimization is a current hot topic. This paper discusses several issues that has not been reported in the static multi-objective optimization literature such as the loss of non-dominated solutions, the emergence of the false non-dominated solutions and the necessity for an online decision-making mechanism. Then, a dynamic multi-objective optimization algorithm is developed, which is inspired by membrane computing. A novel membrane control strategy is proposed in this article and is applied to the optimal control of a time-varying unstable plant. Experimental results clearly illustrate that the control strategy based on the dynamic multi-objective optimization algorithm is highly effective with a short rise time and a small overshoot. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
13. The Complexity of Early Deciding Set Agreement: How can Topology help?
- Author
-
Guerraoui, Rachid and Pochon, Bastian
- Subjects
COMPUTATIONAL complexity ,ALGEBRAIC topology ,DISTRIBUTED algorithms ,COMPUTER science ,MATHEMATICAL analysis ,ALGORITHMS ,MATHEMATICAL optimization - Abstract
Abstract: The aim of this paper is to pose a challenge to the experts of (algebraic) topology techniques. We present an early deciding algorithm that solves the set agreement problem, i.e., the problem which triggered research on applying topology techniques to distributed computing. We conjecture the algorithm to be optimal, and we discuss the need and challenges of applying topology techniques to prove the lower bound. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
14. An intelligent query processing for distributed ontologies
- Author
-
Lee, Jihyun, Park, Jeong-Hoon, Park, Myung-Jae, Chung, Chin-Wan, and Min, Jun-Ki
- Subjects
Algorithm ,Mathematical optimization ,Algorithms ,Computer science - Abstract
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.06.008 Byline: Jihyun Lee (a), Jeong-Hoon Park (a), Myung-Jae Park (a), Chin-Wan Chung (a), Jun-Ki Min (b) Keywords: Distributed query processing; Semantic mapping; Query optimization; Distributed ontologies; Semantic Web Abstract: In this paper, we propose an intelligent distributed query processing method considering the characteristics of a distributed ontology environment. We suggest more general models of the distributed ontology query and the semantic mapping among distributed ontologies compared with the previous works. Our approach rewrites a distributed ontology query into multiple distributed ontology queries using the semantic mapping, and we can obtain the integrated answer through the execution of these queries. Furthermore, we propose a distributed ontology query processing algorithm with several query optimization techniques: pruning rules to remove unnecessary queries, a cost model considering site load balancing and caching, and a heuristic strategy for scheduling plans to be executed at a local site. Finally, experimental results show that our optimization techniques are effective to reduce the response time. Author Affiliation: (a) Division of Computer Science, Department of Electronic Engineering and Computer Science, Korea Advanced Institute of Science and Technology (KAIST), Daejon 305-701, Republic of Korea (b) School of Internet-Media Engineering, Korea University of Technology and Education, Byeongcheon-Myeon, Cheonan, Chungnam 330-708, Republic of Korea Article History: Received 30 October 2008; Revised 30 March 2009; Accepted 7 June 2009
- Published
- 2010
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.