BACKGROUND: Large discrepancies in signature composition and outcome concordance have been observed between different microarray breast cancer expression profiling studies. This is often ascribed to differences in array platform as well as biological variability. We conjecture that other reasons for the observed discrepancies are the measurement error associated with each feature and the choice of preprocessing method. Microarray data are known to be subject to technical variation and the confidence intervals around individual point estimates of expression levels can be wide. Furthermore, the estimated expression values also vary depending on the selected preprocessing scheme. In microarray breast cancer classification studies, however, these two forms of feature variability are almost always ignored and hence their exact role is unclear. RESULTS: We have performed a comprehensive sensitivity analysis of microarray breast cancer classification under the two types of feature variability mentioned above. We used data from six state of the art preprocessing methods, using a compendium consisting of eight different datasets, involving 1131 hybridizations, containing data from both one and two-color array technology. For a wide range of classifiers, we performed a joint study on performance, concordance and stability. In the stability analysis we explicitly tested classifiers for their noise tolerance by using perturbed expression profiles that are based on uncertainty information directly related to the preprocessing methods. Our results indicate that signature composition is strongly influenced by feature variability, even if the array platform and the stratification of patient samples are identical. In addition, we show that there is often a high level of discordance between individual class assignments for signatures constructed on data coming from different preprocessing schemes, even if the actual signature composition is identical. CONCLUSION: Feature variability can have a strong impact on breast cancer signature composition, as well as the classification of individual patient samples. We therefore strongly recommend that feature variability is considered in analyzing data from microarray breast cancer expression profiling experiments.

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost of arbitrary preemptions. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is pessimistic and/or optimistic. The same problem also arises for fixed-priority non-pre-emptive scheduling (FPNS), being a special case of FPDS. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis is based on known concepts of critical instant and busy period for FPPS. To accommodate for our scheduling model for FPDS, we need to slightly modify existing definitions of these concepts. The analysis assumes a continuous scheduling model, which is based on a partitioning of the timeline in a set of non-empty, right semi-open intervals. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Hence, that instant, period, and response time cannot be assumed for any task, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks. These anomalies for the lowest priority task are an immediate consequence of the fact that only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks, illustrates the revised analysis for an advanced model for FPDS, where tasks are structured as flow graphs of subjobs rather than sequences, and shows that our analysis is sustainable.

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority preemptive scheduling (FPPS), that both reduces the cost of arbitrary preemptions and removes the need for non-trivial resource access protocols. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is both pessimistic and optimistic. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis assumes a continuous scheduling model. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks, because only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks.

Recommender systems are increasingly being employed to personalize services, such as on the web, but also in electronics devices, such as personal video recorders. These recommenders learn a user profile, based on rating feedback from the user on, e.g., books, songs, or TV programs, and use machine learning techniques to infer the ratings of new items.

To analyse the schedulability of conditionally guaranteed budgets (CGBs) in the context of fixed-priority preemptive scheduling (FPPS), we present a so-called cognac-glass algorithm (CGA). CGBs have been conceived in the context of software video processing for consumer terminals to exploit the relative importance of applications. CGBs are similar to normal budgets, but are only conditionally guaranteed. This paper presents the schedulability analysis of CGBs under FPPS, based on both best-case and worst-case analysis techniques. We show that because both techniques are used, it is not straightforward to base the analysis on a critical instant. We therefore have to investigate multiple phasings of budgets during the analysis, for which we present a so-called cognac-glass algorithm. We derive that it suffices to consider only a subset of so-called dominating values for the phasing, which improves the efficiency of our algorithm. Given our analysis, we evaluate the effectiveness of CGBs, and conclude that CGBs are particularly useful for software video processing. Finally, we briefly compare our approach for CGBs with existing analysis techniques for hierarchical FPPS, and illustrate that best-case analysis techniques and a CGA can reduce the inherent pessimism in these existing techniques

Many real-time systems needing an online schedulability test requires exact schedulability analysis. In this paper we evaluate standard initial values for the iterative procedure to calculate worst-case response times of periodic tasks under fixed priority preemptive scheduling and arbitrary phasing. For discrete scheduling, we show that the number of iterations needed to determine the worst-case response time of a task using standard initial values increases logarithmically for an increasing worst-case computation time of that task. We present a new initial value, and prove that the number of iterations for that value is bounded. The costs of using the standard and new initial values are compared by means of an experiment. We briefly discuss the applicability of the initial value in other contexts, such as best-case response time analysis and jitter analysis.

Random redundant data storage strategies have proven to be a good choice for efficient data storage in multimedia servers. These strategies lead to a retrieval problem in which it is decided for each requested data block which disk to use for its retrieval. In this paper, we give a complexity classification of retrieval problems for random redundant storage.

We present a two-stage solution approach to the multidimensional periodic scheduling (MPS) problem. This problem originates from the design of high-throughput digital-signal-processor systems, where highly parallel execution of loops is of utmost importance. We introduce the concept of multidimensional periodic operations in order to cope with problems originating from loop hierarchies and explicit timing requirements. In the first stage of the approach, we assign periods to the multidimensional periodic operations such that storage costs are minimized. This is done by means of branch-and-bound, based on a linear programming and constraint-generation technique. In the second stage, we assign start times to the operations and determine on which processing units (PUs) they are executed. This is done by means of an iterative approach. The two major subproblems of MPS concerning checking data dependency constraints and PU constraints are solved by means of an all-integer integer-linear-programming technique. This technique is used as a subroutine in the above two stages. The effectiveness and efficiency of the approach are good, which is illustrated by means of some practical examples.

Article Period assignment in multidimensional periodic scheduling Share on Authors: Wim F. J. Verhaegh Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The NetherlandsView Profile , Emile H. L. Aarts Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands, and Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands, and Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The NetherlandsView Profile , Paul C. N. van Gorp Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The NetherlandsView Profile Authors Info & Claims ICCAD '98: Proceedings of the 1998 IEEE/ACM international conference on Computer-aided designNovember 1998 Pages 585–592https://doi.org/10.1145/288548.289090Published:01 November 1998 2citation134DownloadsMetricsTotal Citations2Total Downloads134Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper addresses the problem of constructing a scan chain such that (1) the area overhead is minimal for latch-based designs, and (2) the number of pipeline scan shifts is minimal. We present an efficient heuristic algorithm to construct near-optimal scan chains. On the theoretical side, we show that part (1) of the problem can be solved in polynomial time, and that part (2) is NP-hard, thus precisely pinpointing the source of complexity and justifying our heuristic approach. Experimental results on three industrial asynchronous IC designs show (1) less than 0.1% extra scan latches for level-sensitive scan design, and (2) scan shift reductions up to 86% over traditional scan schemes.

We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time.

This paper discusses improved force-directed scheduling and its application in the design of high-throughput DSP systems, such as real-time video VLSL circuits. We present a mathematical justification of the technique of force-directed scheduling, introduced by Paulin and Knight (1989), and we show how the algorithm can be used to find cost-effective time assignments and resource allocations, allowing trade-offs between processing units and memories. Furthermore, we present modifications that improve the effectiveness and the efficiency of the algorithm. The significance of the improvements is illustrated by an empirical performance analysis based on a number of problem instances.>

A multiport memory allocation problem for hierarchical, i.e. multi-dimensional, data streams is described. Memory allocation techniques are used in high level synthesis for foreground and background memory allocation, the design of data format converters, and the design of synchronous inter-processor communication hardware. The techniques presented in this paper differ from other approaches in the sense that data streams are considered to be design entities and are not expanded to individual samples. A formal model for hierarchical data streams is given and a memory allocation algorithm is presented. The algorithm comprises two steps: data routing and assignment of signal delays to memories. A number of sub-problems are formulated as ILP programs. In the presented form, the allocation algorithm only considers interconnect costs, but memory size and other cost factors can be taken into account. The presented work is implemented in the memory allocation tool MEDEA which is part of the PHIDEO synthesis system.

Force-directed scheduling is a technique which schedules operations under time constraints in order to achieve schedules with a minimum number of resources. The worst case time complexity of the algorithm is cubic in the number of operations. This is due to the computation of the changes in the distribution functions needed for the force calculations. An incremental way to compute the changes in the distribution functions, based on gradual time-frame reduction, is presented. This reduces the time complexity of the algorithm to quadratic in the number of operations, without any loss in effectiveness or generality of the algorithm. Implementations show a substantial CPU-time reduction of force-directed scheduling, which is illustrated by means of some industrially relevant examples.>

Functions executed by a multifunctional processing unit (PU) correspond to clusters of operations in the specification, which are represented as signal flow graphs (SFGs). Because of high-throughput demands, the operations of each SFG are executed in parallel. Since operations for only one of the SFGs are executed at a given time, operations belonging to different SFGs can be executed on the same operator. Here, the most important part of the mapping of several SFGs onto one PU, which is the assignment of the SFGs operations to the PU's operators, given a number of allocated operators, is considered. The problem is to find an operator assignment that minimizes the silicon area that is occupied by the PU's interconnection consisting of multiplexers and wires. An approach based on local search algorithms such as iterative improvement and simulated annealing is presented. Although these algorithms are known to be generally applicable, it is shown that detailed knowledge of the operator assignment problem is required to obtain good results within acceptable CPU time limits for large problem instances.>