检索结果-内蒙古大学图书馆

High-Throughput Bin Packing: Scheduling Jobs With Random Resource Demands in Clusters

IEEE-ACM TRANSACTIONS ON NETWORKING 2021年第1期29卷 220-233页

作者： Psychas, Konstantinos Ghaderi, Javad Columbia Univ Dept Elect Engn New York NY 10027 USA

We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource demands (e.g. memory requirements) arrive over time and must be served by a cluster of servers. To improve throughput and delay, the scheduler can pack as many jobs as possible in each server, however the sum of the jobs' resource demands cannot exceed the server's capacity. Motivated by the increasing complexity of workloads in shared clusters, we consider a setting where jobs' resource demands belong to a very large set of diverse types, or in the extreme case even infinitely many types, i.e. resource demands are drawn from a general unknown distribution over a possibly continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) type setting. We first characterize a fundamental limit on the maximum throughput in such setting. We then develop oblivious scheduling algorithms, based on Best-Fit and Universal partitioning, that have low complexity and can achieve at least 1/2 and 2/3 of the maximum throughput respectively, without the knowledge of the resource demand distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms.

关键词： Servers Throughput Scheduling Memory management Complexity theory partitioning algorithms Scheduling algorithms Scheduling algorithms stability queues bin packing data centers

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for the Incremental Broad Learning System by Inverse Cholesky Factorization of a Partitioned Matrix

引用

IEEE ACCESS 2021年 9卷 19294-19303页

作者： Zhu, Hufei Liu, Zhulin Chen, C. L. Philip Liang, Yanyang Wuyi Univ Fac Intelligent Mfg Jiangmen 529020 Peoples R China South China Univ Technol Sch Comp Sci & Engn Guangzhou 510640 Peoples R China Univ Macau Fac Sci & Technol Macau Peoples R China

In this paper, we propose an efficient algorithm to accelerate the existing Broad Learning System (BLS) algorithm for new added nodes. The existing BLS algorithm computes the output weights from the pseudoinverse with the ridge regression approximation, and updates the pseudoinverse iteratively. As a comparison, the proposed BLS algorithm computes the output weights from the inverse Cholesky factor of the Hermitian matrix in the calculation of the pseudoinverse, and updates the inverse Cholesky factor efficiently. Since the Hermitian matrix in the definition of the pseudoinverse is smaller than the pseudoinverse, the proposed BLS algorithm can reduce the computational complexity, and usually requires less than 2/3 of complexities with respect to the existing BLS algorithm. Our experiments on the Modified National Institute of Standards and Technology (MNIST) dataset show that the speedups in accumulative training time and each additional training time of the proposed BLS over the existing BLS are 24.81%similar to 37.99% and 36.45%similar to 58.96%, respectively, and the speedup in total training time is 37.99%. In our experiments, the proposed BLS and the existing BLS both achieve the same testing accuracy when the tiny differences (<= 0.05%) caused by the numerical errors are neglected, and the above-mentioned tiny differences and numerical errors become zeroes and ignorable, respectively, when the ridge parameter is not too small.

关键词： Approximation algorithms Training Speech recognition Principal component analysis partitioning algorithms Manufacturing Licenses Broad learning system (BLS) incremental learning added nodes random vector functional-link neural networks (RVFLNN) single layer feedforward neural networks (SLFN) efficient algorithms partitioned matrix inverse Cholesky factorization pseudoinverse

来源：评论

学校读者我要写书评

暂无评论

Insights Into algorithms for Separable Nonlinear Least Squares Problems

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2021年 30卷 1207-1218页

作者： Chen, Guang-Yong Gan, Min Wang, Shuqiang Chen, C. L. Philip Univ Macau Fac Sci & Technol Zhuhai Macau Peoples R China Qingdao Univ Coll Comp Sci & Technol Qingdao 266071 Peoples R China Fuzhou Univ Coll Math & Comp Sci Fuzhou 350108 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China South China Univ Technol Sch Comp Sci & Engn Guangzhou 510641 Peoples R China

Separable nonlinear least squares (SNLLS) problems have attracted interest in a wide range of research fields such as machine learning, computer vision, and signal processing. During the past few decades, several algorithms, including the joint optimization algorithm, alternated least squares (ALS) algorithm, embedded point iterations (EPI) algorithm, and variable projection (VP) algorithms, have been employed for solving SNLLS problems in the literature. The VP approach has been proven to be quite valuable for SNLLS problems and the EPI method has been successful in solving many computer vision tasks. However, no clear explanations about the intrinsic relationships of these algorithms have been provided in the literature. In this paper, we give some insights into these algorithms for SNLLS problems. We derive the relationships among different forms of the VP algorithms, EPI algorithm and ALS algorithm. In addition, the convergence and robustness of some algorithms are investigated. Moreover, the analysis of the VP algorithm generates a negative answer to Kaufman's conjecture. Numerical experiments on the image restoration task, fitting the time series data using the radial basis function network based autoregressive (RBF-AR) model, and bundle adjustment are given to compare the performance of different algorithms.

关键词： Jacobian matrices Optimization Signal processing algorithms partitioning algorithms Bundle adjustment Analytical models Robustness Variable projection separable nonlinear least-squares problem parameter estimation image restoration RBF-AR model bundle adjustment

来源：评论

学校读者我要写书评

暂无评论

Fast CU Partition Decision Strategy Based on Human Visual System Perceptual Quality

引用

IEEE ACCESS 2021年 9卷 123635-123647页

作者： Zhao, Jinchao Cui, Tengyao Zhang, Qiuwen Zhengzhou Univ Light Ind Coll Comp & Commun Engn Zhengzhou 450002 Peoples R China

A fast Coding Unit (CU) partition decision strategy based on Human Visual System (HVS) perception quality is proposed in this paper. Considering that it is difficult for existing fast algorithms to further improve compression efficiency, perceptual coding technology has been tried to remove visual redundancy for achieving the purpose of reducing the bit rate on the basis of maintaining subjective visual quality. However, the existing perceptual coding model is still insufficient to reflect the characteristics of the HVS, which has limited improvement in coding efficiency, especially in fast algorithms. In this method, the characteristics of the limited human capacity for spatial-temporal resolution and the visual sensory memory are used to improve coding performance. First, the color complexity is used as a control factor to optimize the Just Noticeable Difference (JND) model to remove visual redundancy in a way that is more in line with the characteristics of visual perception. Second, a classification model of motion patterns based on human visual saliency is designed to provide a basis for CU classification, which effectively improves the coding accuracy. Finally, an offline Decision Tree (DT) classifier is designed based on the above model, and texture features are incorporated into the classifier as another key attribute to further reduce the computational complexity. The results of performance evaluation confirm that the proposed method achieves significantly improved coding performance compared with original Versatile Test Model (VTM). Compared with existing algorithms, our method not only improves coding efficiency, but also improves subjective visual quality.

关键词： Encoding Visualization Visual perception partitioning algorithms Distortion Color Bit rate VVC fast partition decision just noticeable difference motion pattern classification texture information decision tree

来源：评论

学校读者我要写书评

暂无评论

An Improved Numerical DBSCAN Algorithm Based on Non-IIDness Learning

引用

IEEE ACCESS 2021年 9卷 117052-117066页

作者： Wang, Yanmei Jiang, He Zhou, Huixin Wang, Chengqiang Qilu Univ Technol Sch Comp Sci & Technol Shandong Acad Sci Jinan 250353 Peoples R China

In clustering algorithm research, objects, attributes and other aspects of data sets are usually considered to be independent and identically distributed;that is, each object is assumed to be an independent and uniformly distributed individual with no impacts between objects. However, objects in real life are often neither independently nor identically distributed;that is, they are non-IID, leading to a complex coupling relationship between objects, and objects interact with each other. The results of a clustering algorithm under an independent and identical distribution may be incomplete or even misleading. To make the results of the DBSCAN algorithm as accurate as possible, an improved numerical DBSCAN algorithm based on non-IIDness learning is proposed in this paper. The algorithm calculates the coupling relationship between objects to obtain the potential relationship between objects and determines the parameters Eps and MinPts by the distribution characteristics of the data. Experiments on large-scale real and synthetic data sets show that the algorithm achieves a higher accuracy than the original DBSCAN algorithm and the main algorithms that improved upon it.

关键词： Clustering algorithms Couplings Licenses partitioning algorithms Correlation Time series analysis Sorting Clustering DBSCAN parameter selection non-IIDness learning

来源：评论

学校读者我要写书评

暂无评论

True Load Balancing for Matricized Tensor Times Khatri-Rao Product

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2021年第8期32卷 1974-1986页

作者： Abubaker, Nabil Acer, Seher Aykanat, Cevdet Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey Sandia Natl Labs Albuquerque NM 87123 USA

MTTKRP is the bottleneck operation in algorithms used to compute the CP tensor decomposition. For sparse tensors, utilizing the compressed sparse fibers (CSF) storage format and the CSF-oriented MTTKRP algorithms is important for both memory and computational efficiency on distributed-memory architectures. Existing intelligent tensor partitioning models assume the computational cost of MTTKRP to be proportional to the total number of nonzeros in the tensor. However, this is not the case for the CSF-oriented MTTKRP on distributed-memory architectures. We outline two deficiencies of nonzero-based intelligent partitioning models when CSF-oriented MTTKRP operations are performed locally: failure to encode processors' computational loads and increase in total computation due to fiber fragmentation. We focus on existing fine-grain hypergraph model and propose a novel vertex weighting scheme that enables this model encode correct computational loads of processors. We also propose to augment the fine-grain model by fiber nets for reducing the increase in total computational load via minimizing fiber fragmentation. In this way, the proposed model encodes minimizing the load of the bottleneck processor. Parallel experiments with real-world sparse tensors on up to 1024 processors prove the validity of the outlined deficiencies and demonstrate the merit of our proposed improvements in terms of parallel runtimes.

关键词： Tensors Computational modeling Program processors Load modeling Sparse matrices partitioning algorithms Computational efficiency Load balancing sparse tensors MTTKRP CP decomposition fine-grain hypergraph partitioning

来源：评论

学校读者我要写书评

暂无评论

Hybrid MAP and PIC Detection for OTFS Modulation

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2021年第7期70卷 7193-7198页

作者： Li, Shuangyang Yuan, Weijie Wei, Zhiqiang Yuan, Jinhong Bai, Baoming Ng, Derrick Wing Kwan Xie, Yixuan Univ New South Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia Southern Univ Sci & Technol Dept Elect & Elect Engn Shenzhen 518055 Peoples R China Univ New South Wales Sch Elect Engn & Telecommun Kensington NSW 2052 Australia Friedrich Alexander Univ Erlangen Nuremberg Dept Elect Engn Elect Informat Technol D-91054 Erlangen Germany Xidian Univ State Key Lab ISN Xian 710071 Peoples R China

Orthogonal time frequency space (OTFS) modulation has attracted substantial attention recently due to its great potential of providing reliable communications in high-mobility scenarios. In this article, we propose a novel hybrid signal detection algorithm for OTFS modulation. Based on the system model, we first derive the near-optimal symbol-wise maximum a posteriori (MAP) detection algorithm for OTFS modulation. Then, in order to reduce the detection complexity, we propose a partitioning rule that separates the related received symbols into two subsets for detecting each transmitted symbol, according to the corresponding path gains. According to the partitioning rule, we design the hybrid detection algorithm to exploit the power discrepancy of each subset, where the MAP detection is applied to the subset with larger channel gains, while the parallel interference cancellation (PIC) detection is applied to the subset with smaller channel gains. We also provide the error performance analysis of the proposed hybrid detection algorithm. Simulation results show that the proposed hybrid detection algorithm can not only approach the performance of the near-optimal symbol-wise MAP algorithms, but also offer a substantial performance gain compared with existing algorithms.

关键词： Modulation Delays Complexity theory Time-frequency analysis Detection algorithms partitioning algorithms Approximation algorithms Orthogonal time frequency space (OTFS) reduced-complexity detection sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

Recursive Algorithm to Verify Quasi-Uniform Entropy Vectors and its Applications

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第2期69卷 874-883页

作者： Saleem, Dauood Thakor, Satyajit Tiwari, Anil IIT Mandi Sch Comp & Elect Engn Mandi 175005 Himachal Prades India Natl Instruments Syst India Pvt Ltd Varthur 560103 India

It is of central interest in information theory to determine whether a given vector in the entropy space is an almost entropic vector. This problem can be answered if all the information inequalities are known, but this is an extremely challenging problem. On the other hand, we can establish that a given vector is an entropy vector if we can show the existence of distribution such that the corresponding entropy vector is the same as the given vector. However, there is no known algorithm to solve this problem. Only for the simplest case of binary entropy vectors, an algorithm is known to solve this problem. In this paper, we present a recursive algorithm to determine whether a given vector is a quasi-uniform entropy vector and, if it is, to return a consistent quasi-uniform distribution. We also present two applications of the recursive procedure: (i) to generate all quasi-uniform distributions motivated by the problem of finding the smallest quasi-uniform distribution such that its entropy vector violates the well known Ingleton inequality and (ii) to obtain an entropy vector (not necessarily quasi-uniform) near to a target vector in the entropy space for random variables with given alphabet size.

关键词： Entropy Random variables Cramer-Rao bounds Approximation algorithms partitioning algorithms IEEE Regions Electrical engineering Entropy vectors entropy region quasi-uniform distributions

来源：评论

学校读者我要写书评

暂无评论

Low-Energy Eigenspectrum Decomposition (LEED) of Quantum-Dot Cellular Automata Networks

引用

IEEE TRANSACTIONS ON NANOTECHNOLOGY 2021年 20卷 104-112页

作者： Retallick, Jacob Walus, Konrad Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

The design and understanding of quantum-dot cellular automata (QCA) networks has been largely influenced by limitations in the approximation methods used in common design tools. In some cases, such limitations have led to unrealistic selections of clock zones which are not feasible for nanoscale QCA implementations given current fabrication constraints on clocking electrodes. A better understanding of the behaviour of larger QCA networks of perhaps tens to hundreds of QCA devices is needed. One approach is by investigating the low energy spectrum;however, diagonalization of the system Hamiltonian even in the 2-state approximation is impractical beyond 20 or so devices. In this work, we present a methodology for understanding the spectrum of the full network in terms of contributions from components of the network. We show that important features of the low energy spectrum can be attributed to specific critical components, and present one scheme for decomposing the network into these components. In addition, we address the question of computing the low energy spectrum of large QCA networks. A method based on basis reduction which naturally emerges from the component decomposition is successfully applied to a 49 cell XOR gate with results compared against a density matrix renormalization group implementation.

关键词： Clocks Stationary state Correlation Computer architecture Quantum dots Microprocessors Nanoscale devices Quantum dots nanotechnology approximation methods partitioning algorithms

来源：评论

学校读者我要写书评

暂无评论

Automatic Data Clustering Framework Using Nature-Inspired Binary Optimization algorithms

引用

IEEE ACCESS 2021年 9卷 93703-93722页

作者： Merikhi, Behnaz Soleymani, M. R. Concordia Univ Dept Elect & Comp Engn Montreal PQ H3G 1M8 Canada

Cluster analysis using metaheuristic algorithms has earned increasing popularity over recent years due to the great success of these algorithms in finding high-quality clusters in complex real-world problems. This paper proposes a novel framework for automatic data clustering with the capability of generating clusters with approximately the same maximum distortion using nature-inspired binary optimization algorithms. The inherent problem with clustering using such algorithms is having a huge search space. Therefore, we have also proposed a binary encoding scheme for the particle representation to alleviate this problem. The proposed clustering solution requires no prior knowledge of the number of clusters and proceed with the process based on re-clustering, merging, and modifying the small clusters to compensate for the distortion gap between groups with different sizes. The proposed framework's performance has been evaluated over a wide range of synthetic, real-life, and higher dimensional datasets first by considering four different binary optimization algorithms for the optimizer module. Then, it has also been compared to multiple classical and new clustering solutions and two other automatic clustering techniques in continuous search space in terms of separation and compactness of the clusters by utilizing internal validity measures. The experimental results show the proposed solution is highly efficient in creating well-separated and compact clusters with approximately the same distortion in most datasets. Moreover, the application of the proposed framework to the correlated binary dataset is also reported as a case study. The presence of correlation in a dataset results from the similarity between data points in the same category, such as repeated measurements in remote sensing, crowdsourced multi-view video uploading, and augmented reality. Simplicity, customizability, and flexibility in adding extra conditions to the proposed solution and having a dynamic nu

关键词： Clustering algorithms Optimization partitioning algorithms Distortion Approximation algorithms Particle swarm optimization Heuristic algorithms Automatic data clustering binary search space binary clustering cluster-level constraint distortion dynamic clusters nature-inspired optimization algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：