Memory gradient method with Goldstein line search

In this paper, we present a multi-step memory gradient method with Goldstein line search for unconstrained optimization problems and prove its global convergence under some mild conditions. We also prove the linear convergence rate of the new method when the objective function is uniformly convex. Numerical results show that the new algorithm is suitable to solve large-scale optimization problems and is more stable than other similar methods in practical computation.     

On dynamics of automata with a stack

In this paper we introduce a new dynamical system of a pushdown automaton, called automaton with a stack (AS). We prove that every AS has a periodic configuration by construction of it. Next, we define a special case of an AS, called AS with finite memory and we prove that the AS has a finite memory if and only if it is positively expansive. Furthermore, we prove that every AS with finite memory has shadowing property. Having these two properties, we set a finite-to-one map between an AS with finite memory and some vertex subshift, which gives us a semi-conjugacy between these two systems. Additionally, we define an algorithm to decide if a given graph G describes some AS with finite memory and to calculate maximal depth of a stack.     

Lower Bounds for Dynamic Data Structures on Algebraic RAMs

In a seminal paper of 1989, Fredman and Saks proved lower bounds for some important data-structure problems in the cell probe model. This model assumes that data structures are stored in memory with a known word length. In this paper we consider random access machines (RAMs) that can add, subtract, compare, multiply and divide integer or real numbers, with no size limitation. These are referred to as algebraic RAMs . We prove new lower bounds for two important data-structure problems, union-findand dynamic prefix sums . To this end we apply the generalized Fredman—Saks techniqueintroduced by the authors in a previous paper. The generalized technique relies on a certain well-defined function, Output Variability , that characterizes in some sense the power of the computational model. Fredman and Saks' work implied bounds on output variability for the cell probe model; in this paper we provide the first bounds for algebraic RAMs, and show that they suffice for proving tight lower bounds for useful problems. An important feature of the problems we consider is that in a data structure of size n , the data stored are members of {0,\ldots,n} . This makes the derivation of lower bounds for such problems on a RAM without word-size limitations a particular challenge; previous RAM lower bounds we are aware of depend on the fact that the data for the computation can vary over a large domain.     

TSO内存模型下限界可线性化的可判定性研究

TSO-to-TSO可线性化、TSO-to-SC可线性化和TSO可线性化是Total Store Order（简称TSO）内存模型下可线性化的三个变种。在本文中我们提出了?-限界TSO-to-TSO可线性化和?-限界TSO可线性化,考察了?-限界TSO-to-TSO可线性化、?-限界TSO-to-SC可线性化和?-限界TSO可线性化的验证问题。它们分别是这三种可线性化的限界版本,都使用?-扩展历史,这样的扩展历史对应的执行有着限界数目（不超过?个）的函数调用、函数返回、调用刷出和返回刷出动作。?-扩展历史对应执行中的写动作数目是不限界的,进而执行中使用的存储缓冲区的大小也是不限界的,对应的操作语义是无穷状态迁移系统,所以三个限界版本可线性化的验证问题是不平凡的。 我们将定义在并发数据结构与顺序规约之间的?-限界TSO-to-TSO可线性化、?-限界TSO-to-SC可线性化和?-限界TSO可线性化的验证问题归约到?-扩展历史集合之间的TSO-to-TSO可线性化问题,从而以统一的方式验证了TSO内存模型下可线性化的三个限界版本。验证方法的关键步骤是判定一个并发数据结构是否有一个特定的?-扩展历史。我们证明了这个问题是可判定的,证明方法是将这一问题归约为已知可判定的易失通道机器的控制状态可达问题。本质上,这一归约将每一个函数调用或函数返回动作转化为写、刷出或cas（compare-and-swap）动作。在TSO-to-TSO可线性化的定义中,一个函数调用或函数返回动作会同时影响存储缓冲区和控制状态。为了模拟函数调用或函数返回动作对存储缓冲区的影响,我们在每个函数调用或函数返回动作之后立刻执行一个特定的写动作。这个写动作及其对应的刷出动作模拟了函数调用或函数返回动作对存储缓冲区的影响。我们引入观察者进程,为每个函数调用或函数返回动作“绑定”一个观察者进程的cas动作,以这种方式模拟了函数调用或函数返回动作对控制状态的影响。因此,我们证明了TSO内存模型下可线性化的这三个限界版本都是可判定的。我们进而证明了在TSO内存模型下判定可线性化的这三个限界版本的复杂度都在递归函数的Fast-Growing层级中。我们通过证明已知对应复杂度的单通道简单通道机器的可达问题和TSO内存模型下可线性化的三个限界版本可以互相归约得到这个结论。     

Lower Bounds for Dynamic Data Structures on Algebraic RAMs

Abstract. In a seminal paper of 1989, Fredman and Saks proved lower bounds for some important data-structure problems in the cell probe model. This model assumes that data structures are stored in memory with a known word length. In this paper we consider random access machines (RAMs) that can add, subtract, compare, multiply and divide integer or real numbers, with no size limitation. These are referred to as algebraic RAMs . We prove new lower bounds for two important data-structure problems, union-find and dynamic prefix sums . To this end we apply the generalized Fredman—Saks technique introduced by the authors in a previous paper. The generalized technique relies on a certain well-defined function, Output Variability , that characterizes in some sense the power of the computational model. Fredman and Saks' work implied bounds on output variability for the cell probe model; in this paper we provide the first bounds for algebraic RAMs, and show that they suffice for proving tight lower bounds for useful problems. An important feature of the problems we consider is that in a data structure of size n , the data stored are members of {0,\ldots,n} . This makes the derivation of lower bounds for such problems on a RAM without word-size limitations a particular challenge; previous RAM lower bounds we are aware of depend on the fact that the data for the computation can vary over a large domain.     

Improving effective bandwidth through compiler enhancement of global cache reuse

The performance of modern machines is increasingly limited by insufficient memory bandwidth. One way to alleviate this bandwidth limitation for a given program is to minimize the aggregate data volume the program transfers from memory. In this article we present compiler strategies for accomplishing this minimization. Following a discussion of the underlying causes of bandwidth limitations, we present a two-step strategy to exploit global cache reuse—the temporal reuse across the whole program and the spatial reuse across the entire data set used in that program. In the first step, we fuse computation on the same data using a technique called reuse-based loop fusion to integrate loops with different control structures. We prove that optimal fusion for bandwidth is NP-hard and we explore the limitations of computation fusion using perfect program information. In the second step, we group data used by the same computation through the technique of affinity-based data regrouping, which intermixes the storage assignments of program data elements at different granularities. We show that the method is compile-time optimal and can be used on array and structure data. We prove that two extensions—partial and dynamic data regrouping—are NP-hard problems. Finally, we describe our compiler implementation and experiments demonstrating that the new global strategy, on average, reduces memory traffic by over 40% and improves execution speed by over 60% on two high-end workstations.     

A neural computation model with short-term memory

A study of the memory characteristics of the brain and the computer prompts the creation of a new neuron architecture for neural computation. We hypothesize that neural responses resemble hysteresis loops. The upper and lower halves of the hysteresis loop are described by two sigmoids. Generalizing the two sigmoids to two families of curves accommodates loops of various sizes. This model, which we call the ;hystery model', is capable of memorizing the entire history of its bipolar inputs in an adaptive fashion, with larger memory for longer sequences. We theorize and prove that the hystery model's response converges asymptotically to hysteresis-like loops. A simple application to temporal pattern discrimination demonstrates the nonlinear short-term memory characteristics of the hystery model. This model may have important applications for time-based computations such as control, signal processing and spatiotemporal pattern recognition, especially if it can take advantage of existing hysteresis phenomena in semiconductor materials.     

Speed scaling problems with memory/cache consideration

Speed scaling problems consider energy-efficient job scheduling in processors by adjusting the speed to reduce energy consumption, where power consumption is a convex function of speed (usually, \(P(s) =s^{\alpha }, \alpha =2,3\)). In this work, we study speed scaling problems considering memory/cache. Each job needs some time for memory operation when it is fetched from memory,, and needs less time if fetched from the cache. The objective is to minimize energy consumption while satisfying the time constraints of the jobs. Two models are investigated, the non-cache model and the with-cache model. The non-cache model is a variant of the ideal model, where each job i needs a fixed \(c_i\) time for its memory operation; the with-cache model further considers the cache, a memory device with much faster access time but limited space. The uniform with-cache model is a special case of the with-cache model in which all \(c_i\) values are the same. We provide an \(O(n^3)\) time algorithm and an improved \(O(n^2\log n)\) time algorithm to compute the optimal solution in the non-cache model. For the with-cache model, we prove that it is NP-complete to compute the optimal solution. For the uniform with-cache model with agreeable jobs (later-released jobs do not have earlier deadlines), we derive an \(O(n^4)\) time algorithm to compute the optimal schedule, while for the general case we propose a \((2\alpha \frac{g}{g-1})^{\alpha }/2\)-approximation algorithm in a resource augmentation setting in which the memory operation time can accelerate by at most g times.     

A Theoretical Framework Linking Creativity,Empowerment, and Organizational Memory

Empowerment, creativity, and organizational memory are constructs that have been researched in MIS. While each construct has received individual attention, we have found relatively little research linking them. One of the major edicts of empowerment is delegation of decision making authority to lower-level employees. Increased authority allows employees more freedom to be creative. However, if creative thought is generated but not captured, innovative ideas may be lost. Organizational memory can capture creative ideas as they are generated so that empowered teams can draw upon positive creative experiences. We developed a theoretical model to illuminate the relationships between organizational memory, worker empowerment, and creativity. The model portrays the linkages between empowerment and creativity, creativity and organizational memory, and organizational memory and empowerment. The model was developed based on the literature in each respective area and an interview-based study concerning “empowered” systems development project teams and organizational memory. Analysis of the interview data revealed that empowered workers generate creative solutions to problems. However, creative solutions can only be used for future projects if they are somehow recorded into organizational memory. Organizations that empowered their workforce and embraced creativity reported increased customer satisfaction, waste reduction, and some quality gains. In contrast, those that did not empower reported little or no change. Organizations that recorded creative solutions to problems believe that retrieval of this information could be potentially useful for future projects. Potential challenges faced by organizations classified into each cell are also presented. This classification scheme should prove useful as a guide to organizations examining the potential benefits and pitfalls of worker empowerment and organizational memory.     

The Cortexionist architecture: behavioural intelligence of artificial creatures

Traditionally, producing intelligent behaviours for artificial creatures involves modelling their cognitive abilities. This approach raises two problems. On the one hand, defining manually the agent’s knowledge is a heavy and error-prone task that implies the intervention of the animator. On the other hand, the relationship between cognition and intelligence has not been theoretically nor experimentally proven so far. The ecological approaches provide a solution for these problems, by exploring the links between the creature, its body and its environment. Using an artificial life approach, we propose an original model of memory based on the synthesis of several neuroscience theories. The Cortexionist controller integrates cortex-like structure into a connectionist architecture in order to enhance the agent’s adaptation in a dynamic environment, ultimately leading to the emergence of intelligent behaviour. Initial experiments presented in this paper prove the validity of the model.     

A queue based mutual exclusion algorithm

A new elegant and simple algorithm for mutual exclusion of N processes is proposed. It only requires shared variables in a memory model where shared variables need not be accessed atomically. We prove mutual exclusion by reformulating the algorithm as a transition system (automaton), and applying simulation of automata. The proof has been verified with the higher-order interactive theorem prover PVS. Under an additional atomicity assumption, the algorithm is starvation free, and we conjecture that no competing process is passed by any other process more than once. This conjecture was verified by model checking for systems with at most five processes.     

Sharing Memory between Byzantine Processes Using Policy-Enforced Tuple Spaces

Despite the large amount of Byzantine fault-tolerant algorithms for message-passing systems designed through the years, only recently algorithms for the coordination of processes subject to Byzantine failures using shared memory have appeared. This paper presents a new computing model in which shared memory objects are protected by fine-grained access policies, and a new shared memory object, the Policy-Enforced Augmented Tuple Space (PEATS). We show the benefits of this model by providing simple and efficient consensus algorithms. These algorithms are much simpler and requires less shared memory operations, using also less memory bits than previous algorithms based on ACLs and sticky bits. We also prove that PEATS objects are universal, i.e., that they can be used to implement any other shared memory object, and present lock-free and wait-free universal constructions.     

Fences in weak memory models (extended version)

We present a class of relaxed memory models, defined in Coq, parameterised by the chosen permitted local reorderings of reads and writes, and by the visibility of inter- and intra-processor communications through memory (e.g. store atomicity relaxation). We prove results on the required behaviour and placement of memory fences to restore a given model (such as Sequential Consistency) from a weaker one. Based on this class of models we develop a tool, diy, that systematically and automatically generates and runs litmus tests. These tests can be used to explore the behaviour of processor implementations and the behaviour of models, and hence to compare the two against each other. We detail the results of experiments on Power and a model we base on them.     

闪存数据库系统中一种高效的自适应存储模式

使用闪存作为存储介质成为提高数据库系统性能的一条新途径,为了解决闪存数据库系统存储管理技术中基于日志的更新策略存在查询效率低、日志区空间分配不合理、索引更新代价高等问题,提出了基于Bloom Filter的最新版本预测算法,引入记录定位器结构,提出日志概要结构和基于闪存更新查询代价评估模型的自适应机制。实验证明,该方法能够自适应地划分合理的日志区空间,有效提高查询性能,减少各种非聚集索引的更新代价。     

基于负载牵引和记忆效应的X参数的功放建模

为了更加快速准确地描述带有记忆效应的射频功率放大器,基于传统的X参数模型,结合负载牵引和功放的记忆效应,提出一种新型X参数功放建模方法。新方案首先引入负载反射系数;然后利用双记忆路径模型提取出表征记忆效应的非线性函数替换核函数,采用幅度、负载反射系数与频率三变量作为输出信号的新型前馈（FF）结构建立X参数模型;最后采用阶跃信号代替原始的双音信号提取模型用以达到简化模型提取方法的目的,进而提高模型提取的可行性。经仿真测试CGH40045F功放的数据,利用提出的新型X参数建模方案对功放进行建模,仿真功放的相对误差与传统X参数模型、FF结构X参数模型、FB结构X参数模型相比,均有所减小;与FF结构模型和反馈（FB）结构模型相比,仿真时间分别减少了4.08 s和1.64 s。实验结果表明,该模型能够更加快速有效地拟合带有非线性记忆效应的射频功率放大器。     

Distributed Symbolic Model Checking for μ-Calculus

In this paper we propose a distributed symbolic algorithm for model checking of propositional μ-calculus formulas. μ-calculus is a powerful formalism and μ-calculus model checking can solve many problems, including, for example, verification of (fair) CTL and LTL properties. Previous works on distributed symbolic model checking were restricted to reachability analysis and safety properties. This work thus significantly extends the scope of properties that can be verified distributively, enabling us to use them for very large designs.The algorithm distributively evaluates subformulas. It results in sets of states which are evenly distributed among the processes. We show that this algorithm is scalable and therefore can be implemented on huge distributed clusters of computing nodes. The memory modules of the computing nodes collaborate to create a very large memory space, thus enabling the checking of much larger designs. We formally prove the correctness of the parallel algorithm. We complement the distribution of the state sets by showing how to distribute the transition relation.This research was supported by The Israel Science Foundation (grant number 111/01-2) and by a grant from Intel Academic Relations.     

Learning to Predict by the Methods of Temporal Differences

This article introduces a class of incremental learning procedures specialized for prediction – that is, for using past experience with an incompletely known system to predict its future behavior. Whereas conventional prediction-learning methods assign credit by means of the difference between predicted and actual outcomes, the new methods assign credit by means of the difference between temporally successive predictions. Although such temporal-difference methods have been used in Samuel's checker player, Holland's bucket brigade, and the author's Adaptive Heuristic Critic, they have remained poorly understood. Here we prove their convergence and optimality for special cases and relate them to supervised-learning methods. For most real-world prediction problems, temporal-difference methods require less memory and less peak computation than conventional methods and they produce more accurate predictions. We argue that most problems to which supervised learning is currently applied are really prediction problems of the sort to which temporal-difference methods can be applied to advantage.     

Information flow control in multithread applications based on access control lists

Information flow control models prevent information leakage during the execution of an application. We developed a model OORBAC to control information flows in object-oriented systems. Soon after the development of OORBAC, we identified that the model cannot solve the problems induced by multithreaded applications. We thus adapted the concepts of OORBAC to develop a new information flow control model. It offers the features of OORBAC and solves the problems induced by multithread object-oriented applications. The new model is named MtACL (information flow control model for multithreaded object-oriented applications based on access control lists). The multithreaded problems solved by MtACL include the shared memory problem, the non-interference problem, and the combination leakage problem. This paper presents MtACL and proves that the model solves the multithreaded problems.     

From the theory to the tools: parallel dynamic programming

Dynamic programming is an important paradigm that has been widely used to solve problems in various areas such as control theory, operation research, biology and computer science. We generalize the finite automaton formal model for dynamic programming deriving pipeline parallel algorithms. The optimality of these algorithms is established for the new class of non‐decreasing finite automata. As an intermediate step for the construction of a skeleton for the automatic parallelization of dynamic programming, we have developed a tool for the implementation of pipeline algorithms. The tool maps the processes in the pipeline in the target architecture following a mix of block and cyclic policies adapted to the grain of the machine. Based on the former tool, the automatic parallelization of dynamic programming is straightforward. The use of the model and its associated tools is illustrated with the Single Resource Allocation Problem. The performance and portability of these tools is compared with specific ‘hand made’ code written by experienced programmers. The experimental results on distributed memory and shared distributed memory architectures prove the scalability of the proposed paradigm and its associated tools. Copyright © 2000 John Wiley & Sons, Ltd.     

基于Zigbee无线传感网络冲击波测试系统的设计

鉴于现行冲击波测试方法存在的若干问题,设计了一种将存储测试技术和Zigbee无线网络相融合的冲击波测试系统解决方案。经实验证明,该方案可靠,数据可信,具有较大的实用价值和推广价值。