Wavelength and Waveband Assignment for Ring Networks Based on Parallel Multi‐granularity Hierarchical OADMs

In this paper we study the optimization issues of ring networks employing novel parallel multi‐granularity hierarchical optical add‐drop multiplexers (OADMs). In particular, we attempt to minimize the number of control elements for the off‐line case. We present an integer linear programming formulation to obtain the lower bound in optimization, and propose an efficient heuristic algorithm called global bandwidth resource assignment that is suitable for the design of large‐scale OADM networks.     

Quantitative pharmacophore models with inductive logic programming

Three-dimensional models, or pharmacophores, describing Euclidean constraints on the location on small molecules of functional groups (like hydrophobic groups, hydrogen acceptors and donors, etc.), are often used in drug design to describe the medicinal activity of potential drugs (or ‘ligands’). This medicinal activity is produced by interaction of the functional groups on the ligand with a binding site on a target protein. In identifying structure-activity relations of this kind there are three principal issues: (1) It is often difficult to “align” the ligands in order to identify common structural properties that may be responsible for activity; (2) Ligands in solution can adopt different shapes (or `conformations’) arising from torsional rotations about bonds. The 3-D molecular substructure is typically sought on one or more low-energy conformers; and (3) Pharmacophore models must, ideally, predict medicinal activity on some quantitative scale. It has been shown that the logical representation adopted by Inductive Logic Programming (ILP) naturally resolves many of the difficulties associated with the alignment and multi-conformation issues. However, the predictions of models constructed by ILP have hitherto only been nominal, predicting medicinal activity to be present or absent. In this paper, we investigate the construction of two kinds of quantitative pharmacophoric models with ILP: (a) Models that predict the probability that a ligand is “active”; and (b) Models that predict the actual medicinal activity of a ligand. Quantitative predictions are obtained by the utilising the following statistical procedures as background knowledge: logistic regression and naive Bayes, for probability prediction; linear and kernel regression, for activity prediction. The multi-conformation issue and, more generally, the relational representation used by ILP results in some special difficulties in the use of any statistical procedure. We present the principal issues and some solutions. Specifically, using data on the inhibition of the protease Thermolysin, we demonstrate that it is possible for an ILP program to construct good quantitative structure-activity models. We also comment on the relationship of this work to other recent developments in statistical relational learning. Editors: Tamás Horváth and Akihiro Yamamoto     

A power-aware code-compression design for RISC/VLIW architecture

We studied the architecture of embedded computing systems from the viewpoint of power consumption in memory systems and used a selective-code-compression (SCC) approach to realize our design.Based on t...     

基于计算缓存方法的分子动力学程序性能优化

分子动力学数值模拟程序在现代高性能计算机上的计算效率往往很低,只能发挥系统峰值性能的几个百分点。本文对并行分子动力学程序PMD3D在联想深腾6800超级计算机上进行性能优化。通过性能分析,我们发现粒子相互作用力计算中相互关联的浮点运算严重影响了处理器的指令级并行效率,为此我们应用计算缓存的方法,将大量不规则的浮点计算进行缓存,达到一定规模后再进行向量化计算。这样使得单机性能在优化后提升4倍多,达到处理器峰值性能5.2GFlops的32.3%。最后,在深腾6800的64个节点的256个CPU上进行了并行性能测试,达到峰值运算性能1.3万亿次的27%。     

ILP heuristics and a new exact method for bi-objective 0/1 ILPs: Application to FTTx-network design

Heuristics and metaheuristics are inevitable ingredients of most of the general purpose ILP solvers today, because of their contribution to the significant boost of the performance of exact methods. In the field of bi/multi-objective optimization, to the best of our knowledge, it is still not very common to integrate ILP heuristics into exact solution frameworks. This paper aims to bring a stronger attention of both the exact and metaheuristic communities to still unexplored possibilities for performance improvements of exact and heuristic multi-objective optimization algorithms.We focus on bi-objective optimization problems whose feasible solutions can be described as 0/1 integer linear programs and propose two ILP heuristics, boundary induced neighborhood search (BINS) and directional local branching. Their main idea is to combine the features and explore the neighborhoods of solutions that are relatively close in the objective space. A two-phase ILP-based heuristic framework relying on BINS and directional local branching is introduced. Moreover, a new exact method called adaptive search in objective space (ASOS) is also proposed. ASOS combines features of the ϵ-constraint method with the binary search in the objective space and uses heuristic solutions produced by BINS for guidance. Our new methods are computationally evaluated on two problems of particular relevance for the design of FTTx-networks. Comparison with other known exact methods (relying on the exploration of the objective space) is conducted on a set of realistic benchmark instances representing telecommunication access networks from Germany.     

多关系数据挖掘研究综述

多关系数据挖掘是近年来快速发展的重要的数据挖掘领域之一。传统的数据挖掘方法只能完成单一关系中的模式发现,多关系数据挖掘能够从复杂结构化数据中发现涉及多个关系的复杂模式。该文综述了多关系数据挖掘的研究状况。首先分析了多关系数据挖掘领域发生的原因和背景,其次总结了多关系数据挖掘研究的一般方法,然后介绍、分析了最具代表性的多关系数据挖掘算法。最后,总结了多关系数据挖掘将来发展需重点解决的问题和面临的挑战。     

基于简化Trace的动态隐式断言执行

分支指令与分支预测失败限制了处理器发掘指令级并行(ILP)的潜力.通过If-conversion或Predicated执行将程序中的控制相关转化为数据相关,能较好地降低分支预测开销.提出一种基于简化Trace结构的动态隐式断言执行机制(Dynamic Implicit Predication,DIP),而早期的相关研究主要集中于由编译器显式为宽发射处理器产生静态Predicated指令.无需编译器或者其他二进制工具的帮助,DIP可以在程序运行过程中识别可以进行断言变换的指令片断,完成指令转换与优化,并在以后的执行中使用优化后的指令Trace.基于SPEC2000模拟测试表明DIP可以有效避免错误的分支预测,提高并行度,单个程序的IPC平均提高10.3%,基准程序的平均加速比可达7.59%.     

多关系关联规则算法综述

多关系数据挖掘是借鉴ILP技术,并结合机器学习方法所提出的数据挖掘新课题。多关系关联规则是多关系方法在概念描述任务中最具代表性的研究方向之一,此类方法在发挥多关系方法的模式表达能力与利用背景知识能力的同时,借鉴成熟的关联规则方法的思想与优化策略,取得了较高的性能与表达复杂模式的能力,同时在面向复杂结构数据的应用中获得了较好的效果。在简述多关系方法的基础上,通过分析与比较目前具有代表性的多关系关联规则算法,总结了各算法的优势与不足,并指出了该领域目前的主要热点问题。     

Design Alternatives of Multithreaded Architecture

This paper compares two possible implementations of multithreaded architecture and proposes a new architecture combining the flexibility of the first with the low hardware complexity of the second. We present performance and step-by-step complexity analysis of two design alternatives of multithreaded architecture: dynamic inter-thread resource scheduling and static resource allocation. We then introduce a new multithreaded architecture based on a new scheduling mechanism called the semi-static. We show that with two concurrent threads the dynamic scheduling processor achieves from 5 to 45 % higher performance at the cost of much more complicated design. This paper indicates that for a relatively high number of execution resources the complexity of the dynamic scheduling logic will inevitably require design compromises. Moreover, high chip-wide communication time and an incomplete bypassing network will limit the dynamic scheduling and reduce its performance advantage. On the other hand, static scheduling architecture achieves low resource utilization. The semi-static architecture utilizes compiler techniques to exploit patterns of program parallelism and introduces a new hardware mechanism, in order to achieve performance close to dynamic scheduling without significantly increasing the static hardware complexity. The semi-static architecture statically assigns part of the functional units but dynamically schedules the most performance-critical functional units on a medium-grain basis.     

Configuring Traffic Grooming VPλNs

A VPN is an optical virtual private network (oVPN) built of wavelength paths within a multihop wavelength routing (WR) dense wavelength division multiplexing (DWDM) network. An efficient and general graph-theoretic model (the wavelength-graph (WG)) has been proposed along with an integer linear programming (ILP) formulation of setting up VPNs with given traffic requirements over a given WR-DWDM network with two protection scenarios. Here, we have exploited the advantages of traffic grooming, i.e., numerous traffic streams of a VPN can share a wavelength path. We have also generalized the model for setting up VPNs over a WR-DWDM system where multiple VPNs can share a single wavelength path. The objective of the optimization is in all cases to reduce resource usage at upper (electrical) layers (i.e., to reduce the load of the virtual routers), subject to constrained amount of capacity of each wavelength channel and limited number of wavelengths. Here, we propose and compare three basic methods for configuring oVPNs and investigate various parameter settings.