Artificial Intelligence systems are increasingly deployed in settings where ensuring robustness, fairness, or domain-specific properties is essential for regulation compliance and alignment with human values. However, especially on Neural Networks, property enforcement is very challenging, and existing methods are limited to specific constraints or local properties (defined around datapoints), or fail to provide full guarantees. We tackle these limitations by extending SMiLE, a recently proposed enforcement framework for NNs, to support global relational properties (defined over the entire input space). The proposed approach scales well with model complexity, accommodates general properties and backbones, and provides full satisfaction guarantees. We evaluate SMiLE on monotonicity, global robustness, and individual fairness, on synthetic and real data, for regression and classification tasks. Our approach is competitive with property-specific baselines in terms of accuracy and runtime, and strictly superior in terms of generality and level of guarantees. Overall, our results emphasize the potential of the SMiLE framework as a platform for future research and applications.

Background: Real-world optimization problems often contain parameters that are unknown at solving time. For example, in delivery problems, these parameters may be travel times or customer demands. A common strategy in such scenarios is to first predict the parameter values from contextual features using a machine learning model, and then solve the resulting optimization problem. To train the machine learning model, two paradigms can be distinguished. In prediction-focused learning, the model is trained to maximize predictive accuracy. However, this can lead to suboptimal decision-making, because it does not account for how prediction errors affect the quality of the downstream decisions. To address this, decision-focused learning (DFL) minimizes a task loss that captures how the predictions affect decision quality. Objectives: One challenge in DFL is that the task loss has zero-valued gradients when the optimization problem is combinatorial, which hinders gradient-based training. For this reason, state-of-the-art DFL methods use surrogate losses and problem smoothing. However, these methods make specific assumptions about the problem structure (e.g., linear or convex problems with unknown parameters occurring only in the objective function). The goal of our work is to overcome these limitations and extend the applicability of DFL. Method: We propose an alternative DFL approach that makes only minimal assumptions by combining stochastic smoothing with score function gradient estimation. This makes the approach broadly applicable, including to problems with nonlinear objectives, uncertainty in the constraints, and two-stage stochastic optimization problems. Results: Our experiments show that our method matches or outperforms specialized methods for the problems they are designed for, while also extending to settings where no existing method is applicable. In addition, our method always outperforms models trained with prediction-focused learning. Conclusions: In this work we demonstrate that by combining stochastic smoothing and score function gradient estimation to estimate the gradients of a smoothed loss, we can train a machine learning model in a DFL fashion without assuming any structural property of the optimization problem. This approach extends the applicability of DFL to a wider range of optimization problems, including those with uncertainty in the constraints. At the same time, it achieves performance that is competitive with or superior to existing DFL methods when they are applicable.

Despite the extent of recent advances in Machine Learning (ML) and Neural Networks, providing formal guarantees on the behavior of these systems is still an open problem, and a crucial requirement for their adoption in regulated or safety-critical scenarios. We consider the task of training differentiable ML models guaranteed to satisfy designer-chosen properties, stated as input-output implications. This is very challenging, due to the computational complexity of rigorously verifying and enforcing compliance in deep neural models. We provide an innovative approach based on: 1) a general, simple architecture enabling efficient verification with a conservative semantic; 2) a rigorous training algorithm based on the Projected Gradient Method; 3) a formulation of the problem of searching for strong counterexamples. The proposed framework, being only marginally affected by model complexity, scales well to practical applications, and produces models that provide full property satisfaction guarantees. We evaluate our approach on properties defined by linear inequalities in regression, and on mutually exclusive classes in multi-label classification. Our approach is competitive with a baseline that includes property enforcement in preprocessing (on training data) and postprocessing (on model predictions). Finally, our contributions establish a framework that opens up multiple research directions and potential improvements.

Recent developments in algorithmic fairness started to investigate the interaction between multiple sensitive information through an intersectional perspective. We introduce a new definition of intersectional fairness based on a multivariate extension of the Generalized Disparate Impact (GeDI). Our approach leverages a neural network to transform multiple protected groups into a univariate latent space that maximizes correlation with the target, effectively capturing unfairness across all potential subgroups even with limited data samples. Empirical evaluations on several benchmarks demonstrate that our method can be effectively used as a loss regularizer during neural network training, offering stronger performance guarantees compared to existing intersectional statistical parity definitions while also allowing to manage continuous inputs and targets.

Language is typically modelled with discrete sequences. However, the most successful approaches to language modelling, namely neural networks, are continuous and smooth function approximators. In this work, we show that Transformer-based language models implicitly learn to represent sentences as continuous-time functions defined over a continuous input space. This phenomenon occurs in most state-of-the-art Large Language Models (LLMs), including Llama2, Llama3, Phi3, Gemma, Gemma2, and Mistral, and suggests that LLMs reason about language in ways that fundamentally differ from humans. Our work formally extends Transformers to capture the nuances of time and space continuity in both input and output space. Our results challenge the traditional interpretation of how LLMs understand language, with several linguistic and engineering implications.

The integration of constraint programming (CP) together with machine learning (ML) has emerged as a promising direction for tackling complex decision-making and combinatorial optimization problems. While CP offers expressive modeling capabilities and formal guarantees, ML provides adaptive methods for learning from data and generalizing across instances. This survey presents a comprehensive overview of recent advances in combining CP and ML. We first show how ML has been used to improve the CP toolbox, both in modeling and in the efficiency of solving. Then, we examine how CP can support ML, particularly in providing structure, guarantees, and symbolic reasoning capabilities. Finally, we identify key open challenges inherent to such hybrid approaches and outline promising directions for future research. This survey provides a first conceptual and structured review of recent advancements in this emerging field, aiming to serve as a resource for practitioners and researchers in both the CP and ML communities. To keep the progress up to date, a curated list of references is hosted on an accompanying repository (https://github.com/corail-research/CPML-paper-list) and is open to community contributions.

The integration of Machine Learning (ML) and Constrained Optimization (CO) techniques has recently gained significant interest. While pure CO methods struggle with scalability and robustness, and ML methods like constrained Reinforcement Learning (RL) face difficulties with combinatorial decision spaces and hard constraints, a hybrid approach shows promise. However, multi-stage decision-making under uncertainty remains challenging for current methods, which often rely on restrictive assumptions or specialized algorithms. This paper introduces unify , a versatile framework for tackling a wide range of problems, including multi-stage decision-making under uncertainty, using standard ML and CO components. unify integrates a CO problem with an unconstrained ML model through parameters controlled by the ML model, guiding the decision process. This ensures feasible decisions, minimal costs over time, and robustness to uncertainty. In the empirical evaluation, unify demonstrates its capability to address problems typically handled by Decision Focused Learning, Constrained RL, and Stochastic Optimization. While not always outperforming specialized methods, unify ’s flexibility offers broader applicability and maintainability . The paper includes the method’s formalization and empirical evaluation through case studies in energy management and production scheduling, concluding with future research directions.

In the context of mobile and Internet of Things (IoT) networks, data naturally originates at the edge, making crowdsourcing a convenient and inherent approach to data collection. However, crowdsourcing presents challenges related to privacy, sampling bias, statistical sufficiency, and the need for time-consuming post-processing. To this end, generating synthetic data using deep learning techniques emerges as a promising solution to overcome such limitations. In this study, we propose an innovative framework that transcends applications and data types, enabling the conditional generation of crowdsourced datasets with location information in mobile and IoT networks. A crucial aspect of our methodology lies in the ability to assess uncertainty in newly generated samples and produce calibrated predictions through approximate Bayesian methods. Without loss of generality, we ascertain the validity of our method on the task of minimization of drive test (MDT) data generation, presenting for the first time a comparison of synthetically generated data with an original large-scale MDT set collected from a mobile network operator's network infrastructure. By offering a versatile solution to data generation, our framework contributes to overcoming challenges associated with crowdsourced data, opening up possibilities for advanced analytics and experimentation in mobile and IoT networks.

We make two contributions in the field of AI fairness over continuous protected attributes. First, we show that the Hirschfeld-Gebelein-Renyi (HGR) indicator (the only one currently available for such a case) is valuable but subject to a few crucial limitations regarding semantics, interpretability, and robustness. Second, we introduce a family of indicators that are: 1) complementary to HGR in terms of semantics; 2) fully interpretable and transparent; 3) robust over finite samples; 4) configurable to suit specific applications. Our approach also allows us to define fine-grained constraints to permit certain types of dependence and forbid others selectively. By expanding the available options for continuous protected attributes, our approach represents a significant contribution to the area of fair artificial intelligence.

In the context of adversarial robustness, we make three strongly related contributions. First, we prove that while attacking ReLU classifiers is $\mathit{NP}$-hard, ensuring their robustness at training time is $\Sigma^2_P$-hard (even on a single example). This asymmetry provides a rationale for the fact that robust classifications approaches are frequently fooled in the literature. Second, we show that inference-time robustness certificates are not affected by this asymmetry, by introducing a proof-of-concept approach named Counter-Attack (CA). Indeed, CA displays a reversed asymmetry: running the defense is $\mathit{NP}$-hard, while attacking it is $\Sigma_2^P$-hard. Finally, motivated by our previous result, we argue that adversarial attacks can be used in the context of robustness certification, and provide an empirical evaluation of their effectiveness. As a byproduct of this process, we also release UG100, a benchmark dataset for adversarial attacks.

The error robustness of Convolutional Neural Networks (CNNs) is an important attribute requiring attention due to their growing application in safety-critical domains such as autonomous driving and medical devices. Hardware errors affecting the execution of such models may lead to system failures and, therefore, fault tolerance techniques are necessary to improve dependability. This paper proposes an approach to improve the robustness of CNNs and experimentally compares it with three other existing techniques. Fault injection is used to emulate hardware faults affecting CNNs targeting four distinct datasets. Results indicate that the ranger technique globally provides the best robustness closely followed by the stimulated training technique, although the former provides much lower temporal overhead than the latter. Architectural redundancy and dropout provide varying results. In all cases, caution through final evaluation of any CNN is required, because there are corner cases in which the robustness decreases, contrary to the intended outcome.

Adding constraint support in Machine Learning has the potential to address outstanding issues in data-driven AI systems, such as safety and fairness. Existing approaches typically apply constrained optimization techniques to ML training, enforce constraint satisfaction by adjusting the model design, or use constraints to correct the output. Here, we investigate a different, complementary, strategy based on "teaching" constraint satisfaction to a supervised ML method via the direct use of a state-of-the-art constraint solver: this enables taking advantage of decades of research on constrained optimization with limited effort. In practice, we use a decomposition scheme alternating master steps (in charge of enforcing the constraints) and learner steps (where any supervised ML model and training algorithm can be employed). The process leads to approximate constraint satisfaction in general, and convergence properties are difficult to establish; despite this fact, we found empirically that even a naive setup of our approach performs well on ML tasks with fairness constraints, and on classical datasets with synthetic constraints.

Many decision-making processes involve solving a combinatorial optimization problem with uncertain input that can be estimated from historic data. Recently, problems in this class have been successfully addressed via end-to-end learning approaches, which rely on solving one optimization problem for each training instance at every epoch. In this context, we provide two distinct contributions. First, we use a Noise Contrastive approach to motivate a family of surrogate loss functions, based on viewing non-optimal solutions as negative examples. Second, we address a major bottleneck of all predict-and-optimize approaches, i.e. the need to frequently recompute optimal solutions at training time. This is done via a solver-agnostic solution caching scheme, and by replacing optimization calls with a lookup in the solution cache. The method is formally based on an inner approximation of the feasible space and, combined with a cache lookup strategy, provides a controllable trade-off between training time and accuracy of the loss approximation. We empirically show that even a very slow growth rate is enough to match the quality of state-of-the-art methods, at a fraction of the computational cost.

This paper considers multi-stage optimization problems under uncertainty that involve distinct offline and online phases. In particular it addresses the issue of integrating these phases to show how the two are often interrelated in real-world applications. Our methods are applicable under two (fairly general) conditions: 1) the uncertainty is exogenous; 2) it is possible to define a greedy heuristic for the online phase that can be modeled as a parametric convex optimization problem. We start with a baseline composed by a two-stage offline approach paired with the online greedy heuristic. We then propose multiple methods to tighten the offline/online integration, leading to significant quality improvements, at the cost of an increased computation effort either in the offline or the online phase. Overall, our methods provide multiple options to balance the solution quality/time trade-off, suiting a variety of practical application scenarios. To test our methods, we ground our approaches on two real cases studies with both offline and online decisions: an energy management problem with uncertain renewable generation and demand, and a vehicle routing problem with uncertain travel times. The application domains feature respectively continuous and discrete decisions. An extensive analysis of the experimental results shows that indeed offline/online integration may lead to substantial benefits.

The growing demands of the worldwide IT infrastructure stress the need for reduced power consumption, which is addressed in so-called transprecision computing by improving energy efficiency at the expense of precision. For example, reducing the number of bits for some floating-point operations leads to higher efficiency, but also to a non-linear decrease of the computation accuracy. Depending on the application, small errors can be tolerated, thus allowing to fine-tune the precision of the computation. Finding the optimal precision for all variables in respect of an error bound is a complex task, which is tackled in the literature via heuristics. In this paper, we report on a first attempt to address the problem by combining a Mathematical Programming (MP) model and a Machine Learning (ML) model, following the Empirical Model Learning methodology. The ML model learns the relation between variables precision and the output error; this information is then embedded in the MP focused on minimizing the number of bits. An additional refinement phase is then added to improve the quality of the solution. The experimental results demonstrate an average speedup of 6.5% and a 3% increase in solution quality compared to the state-of-the-art. In addition, experiments on a hardware platform capable of mixed-precision arithmetic (PULPissimo) show the benefits of the proposed approach, with energy savings of around 40% compared to fixed-precision.

In this work we consider optimization problems that require to make interdependent offline and online decisions under uncertainty.We broadly refer to long-term strategic decisions as offline and to short-term operational decisions as online.For example, in Distributed Energy Management Systems we may need to define (offline) a daily production schedule for an industrial plant, and then manage (online) its power supply on a hour by hour basis.Traditionally offline and online phases are tackled in isolation, leading to some drawbacks: offline decisions are taken without regard for the capabilities of the downstream online solver; while the applicability of the best approaches for online decisions (e.g.anticipatory algorithms) is limited by the need to provide high responsiveness.Starting from a (literature-based) baseline, we define general methods for leading to significant quality improvements, at the cost of an increased computation effort either in the offline or the online phase.All our methods have broad applicability, and provide multiple options to balance the solution quality/time trade-off, suiting a variety of practical application scenarios with both offline and online decisions and featuring continuous and discrete decisions.An extensive analysis of the experimental results shows that offline/online integration may lead to substantial benefits.

Optimization problems under uncertainty are traditionally solved either via offline or online methods. Offline approaches can obtain high-quality robust solutions, but have a considerable computational cost. Online algorithms can react to unexpected events once they are observed, but often run under strict time constraints, preventing the computation of optimal solutions. Many real world problems, however, have both offline and online elements: a substantial amount of time and information is frequently available (offline) before an online problem is solved (e.g. energy production forecasts, or historical travel times in routing problems); in other cases both offline (i.e. strategic) and online (i.e. operational) decisions need to be made. Surprisingly, the interplay of these offline and online phases has received little attention: like in the blind men and the elephant tale, we risk missing the whole picture, and the benefits that could come from integrated offline/online optimization. In this survey we highlight the potential shortcomings of pure methods when applied to mixed offline/online problems, we review the strategies that have been designed to take advantage of this integration, and we suggest directions for future research.

Anomaly detection in supercomputers is a very difficult problem due to the big scale of the systems and the high number of components. The current state of the art for automated anomaly detection employs Machine Learning methods or statistical regression models in a supervised fashion, meaning that the detection tool is trained to distinguish among a fixed set of behaviour classes (healthy and unhealthy states).We propose a novel approach for anomaly detection in HighPerformance Computing systems based on a Machine (Deep) Learning technique, namely a type of neural network called autoencoder. The key idea is to train a set of autoencoders to learn the normal (healthy) behaviour of the supercomputer nodes and, after training, use them to identify abnormal conditions. This is different from previous approaches which where based on learning the abnormal condition, for which there are much smaller datasets (since it is very hard to identify them to begin with).We test our approach on a real supercomputer equipped with a fine-grained, scalable monitoring infrastructure that can provide large amount of data to characterize the system behaviour. The results are extremely promising: after the training phase to learn the normal system behaviour, our method is capable of detecting anomalies that have never been seen before with a very good accuracy (values ranging between 88% and 96%).

Sampling-based anticipatory algorithms can be very effective at solving online optimization problems under uncertainty, but their computational cost may be prohibitive in some cases. Given an arbitrary anticipatory algorithm, we present three methods that allow to retain its solution quality at a fraction of the online computational cost, via a substantial degree of offline preparation. Our approaches are obtained by combining: 1) a simple technique to identify likely future outcomes based on past observations; 2) the (expensive) offline computation of a "contingency table"; and 3) an efficient solution-fixing heuristic. We ground our techniques on two case studies: an energy management system with uncertain renewable generation and load demand, and a traveling salesman problem with uncertain travel times. In both cases, our techniques achieve high solution quality, while substantially reducing the online computation time.

Kidney exchange programs enable willing, but incompatible, donor-patient pairs to swap donors, thus allowing persons suffering from organ failure to access transplantation. Choosing which pairs to match requires solving a stochastic online optimization problem where patients and donors arrive over time. Despite this, most of the related scientific literature has focused on deterministic offline models. In this paper, we present a simple approach to employ a model for the offline Kidney Exchange Problem (KEP) as the basis of an on-line anticipatory algorithm. Our approach grounds on existing techniques for the on-line KEP, but it generalizes them and provides a more accurate estimate of the expected impact of current decisions. In an experimentation based on a state-of-the-art donor pool generation method, the approach provides improvements in terms of quality and is able to deal with realistic instance size in reasonable time.

In the past few years, the area of Machine Learning (ML) has witnessed tremendous advancements, becoming a pervasive technology in a wide range of applications. One area that can significantly benefit from the use of ML is Combinatorial Optimization. The three pillars of constraint satisfaction and optimization problem solving, i.e., modeling, search, and optimization, can exploit ML techniques to boost their accuracy, efficiency and effectiveness. In this survey we focus on the modeling component, whose effectiveness is crucial for solving the problem. The modeling activity has been traditionally shaped by optimization and domain experts, interacting to provide realistic results. Machine Learning techniques can tremendously ease the process, and exploit the available data to either create models or refine expert-designed ones. In this survey we cover approaches that have been recently proposed to enhance the modeling process by learning either single constraints, objective functions, or the whole model. We highlight common themes to multiple approaches and draw connections with related fields of research.

In this work we present two general techniques to deal with multi-stage optimization problems under uncertainty, featuring off-line and on-line decisions. The methods are applicable when: 1) the uncertainty is exogenous; 2) there exists a heuristic for the on-line phase that can be modeled as a parametric convex optimization problem. The first technique replaces the on-line heuristics with an anticipatory solver, obtained through a systematic procedure. The second technique consists in making the off-line solver aware of the on-line heuristic, and capable of controlling its parameters so as to steer its behavior. We instantiate our approaches on two case studies: an energy management system with uncertain renewable generation and load demand, and a vehicle routing problem with uncertain travel times. We show how both techniques achieve high solution quality w.r.t. an oracle operating under perfect information, by obtaining different trade-offs in terms of computation time.

Scheduling and dispatching are critical enabling technologies in supercomputing and grid computing. In these contexts, scalability is an issue: we have to allocate and schedule up to tens of thousands of tasks on tens of thousands of resources. This problem scale is out of reach for complete and centralized scheduling approaches.

Scheduling and dispatching tools for high-performance computing (HPC) machines have the key role of mapping jobs to the available resources, trying to maximize performance and quality-of-service (QoS). Allocation and Scheduling in the general case are well-known NP-hard problems, forcing commercial schedulers to adopt greedy approaches to improve performance and QoS. Search-based approaches featuring the exploration of the solution space have seldom been employed in this setting, but mostly applied in off-line scenarios. In this paper, we present the first search-based approach to job allocation and scheduling for HPC machines, working in a production environment. The scheduler is based on Constraint Programming, an effective programming technique for optimization problems. The resulting scheduler is flexible, as it can be easily customized for dealing with heterogeneous resources, user-defined constraints and different metrics. We evaluate our solution both on virtual machines using synthetic workloads, and on the Eurora HPC with production workloads. Tests on a wide range of operating conditions show significant improvements in waitings and QoS in mid-tier HPC machines w.r.t state-of-the-art commercial rule-based dispatchers. Furthermore, we analyze the conditions under which our approach outperforms commercial approaches, to create a portfolio of scheduling algorithms that ensures robustness, flexibility and scalability.

Effective multicore computing requires to make efficient usage of the computational resources on a chip. Offline mapping and scheduling can be applied to improve the performance, but classical approaches require considerable a priori knowledge of the target application. In a practical setting, precise information is often unavailable; one can then resort to approximate time and resource usage figures, but this usually requires to make conservative assumptions. The issue is further stressed if real-time guarantees must be provided. We tackle predictable and efficient nonpreemptive scheduling of multitask applications in the presence of duration uncertainty. Hard real-time guarantees are provided with limited idle time insertion, by exploiting a hybrid offline/online technique known as Precedence Constraint Posting (PCP). Our approach does not require probability distributions to be specified, relying instead on simple and cheaper-to-obtain information (bounds, average values). The method has been tested on synthetic applications/platforms and compared with an offline optimized Fixed Priority Scheduling (FPS) approach and a pure online FIFO scheduler; the results are very promising, as the PCP schedules exhibit good stability and improved average execution time (14 percent on average, up to 30 percent versus FPS and up to 40 percent versus the FIFO scheduler).

Although successfully employed on many industrial problems, Combinatorial Optimization still has limited applicability on several real-world domains, often due to modeling difficulties. This is typically the case for systems under the control of an on-line policy: even when the policy itself is well known, capturing its effect on the system in a declarative model is often impossible by conventional means. Such a difficulty is at the root of the classical, sharp separation between off- line and on-line approaches. In this paper, we investigate a general method to model controlled systems, based on the integration of Machine Learning and Constraint Programming (CP). Specifically, we use an Artificial Neural Network (ANN) to learn the behavior of a controlled system (a multicore CPU with thermal con- trollers) and plug it into a CP model by means of Neuron Constraints. The method obtains significantly better results compared to an approach with no ANN guidance. Neuron Constraints were first introduced in [Bartolini et al., 2011b] as a mean to model complex systems: providing evidence of their applicability to controlled systems is a significant step forward, broadening the application field of combinatorial methods and disclosing opportunities for hybrid off-line/on-line optimization.

We investigate the impact of information extracted from sampling and diving on the solution of Constraint Satisfaction Problems (CSP). A sample is a complete assignment of variables to values taken from their domain according to a given distribution.

Recent advances in biosensing technologies have led to applications of biosensor probe arrays for rapid identification of biological agents such as drugs, gene expressions, proteins, cholesterol and fats in an input sample. However, monitoring the simultaneous presence of multiple agents in a sample is still a challenging task. Multiple agents may often attach to the same probes, leading to low specificity. By using microarrays as a specific example, we introduce two methods based on conditional deduction and non-unique probes to detect multiple targets. We introduce three quality metrics, namely: effectiveness, cost and reliability to evaluate different designs of microarrays and propose two ILP/Pseudo-Boolean models for optimizing on these metrics. By applying on various synthetic and real datasets, we demonstrate the importance of these quality metrics in designing microarrays for multiple target detections.

Our work focuses on allocating and scheduling a synchronous data-flow (SDF) graph onto a multi-core platform subject to a minimum throughput requirement. This problem has traditionally be tackled by incomplete approaches based on problem decomposition and local search, which could not guarantee optimality. Exact algorithms used to be considered reasonable only for small problem instances. We propose a complete algorithm based on Constraint Programming which solves the allocation and scheduling problem as a whole. We introduce a number of search acceleration techniques that significantly reduce run-time by aggressively pruning the search space without compromising optimality. The solver has been tested on a number of non-trivial instances and demonstrated promising run-times on SDFGs of practical size and one order of magnitude speed-up w.r.t. the fastest known complete approach.

Scheduling task graphs under hard (end-to-end) timing constraints is an extensively studied NP-hard problem of critical importance for predictable software mapping on Multiprocessor System-on-chip (MPSoC) platforms. In this work we focus on an off-line (design-time) version of this problem, where the target task graph is known before execution time. We address the issue of scheduling robustness, i.e. providing hard guarantees that the schedule will meet the end-to-end deadline in presence of bounded variations of task execution times expressed as min-max intervals known at design time. We present a robust scheduling algorithm that proactively inserts sequencing constraints when they are needed to ensure that execution will have no inserted idle times and will meet the deadline for any possible combination of task execution times within the specified intervals. The algorithm is complete, i.e. it will return a feasible graph augmentation if one exists. Moreover, we provide an optimization version of the algorithm that can compute the shortest deadline that can be met in a robust way.

The Cell BE processor provides both scalable computation power and flexibility, and it is already being adopted for many computational intensive applications. Despite of its merits, it also presents many challenges, as it is now widely known that is very difficult to program the Cell BE in an efficient manner. Hence, the creation of an efficient software development framework is becoming the key challenge for this computational platform. We propose a novel software toolkit, called Cellflow, which enables developers to quickly build multi-task applications for Cell-based platform. We support programmers from the initial stage of their work, through a development-time software infrastructure, to the final stage of the application development, proposing a safe and easy-to-use explicit parallel programming model. Experimental results show that in Cellflow we reduced to minimum the abstraction gap between the optimization and development phases.

The increasing levels of system integration in Multi-Processor System-on-Chips (MPSoCs) emphasize the need for new design flows for efficient mapping of multi-task applications onto hardware platforms. Even though data-flow graphs are often used for pure data-streaming, many realistic applications can only be specified as conditional task graphs (CTG). The problem of allocating and scheduling conditional task graphs on processors in a distributed real-time system is NP-hard. The first contribution of this paper is a complete stochastic allocation and scheduling framework, where an MPSoC virtual platform is used to accurately derive input parameters, validate abstract models of system components and assess constraint satisfaction and objective function optimization. The optimizer implements an efficient and exact approach to allocation and scheduling based on problem decomposition. The original contributions of the approach appear both in the allocation and in the scheduling part of the optimizer. For the first, we propose an exact analytic formulation of the stochastic objective function based on the task graph analysis, while for the scheduling part we extend the timetable constraint for conditional activities. The second contribution of this paper is the introduction of a software library and API for the deployment of conditional task graph applications onto Multi-Processor System-on-Chips. With our library support, programmers can quickly develop multi-task applications which will run on a multi-core architecture and can easily apply the optimal solution found by our optimizer. The proposed programming support manages OS-level issues, such as task allocation and scheduling, as well as task-level issues, like inter-task communication and synchronization.