OCA

or how to help make the right decisions faster...

This project lies at the intersection of operational research and parallel computing. The goal is to investigate the role of accelerators in addressing key problems in operational research, and more specifically, difficult combinatorial optimization problems.

Operations Research (OR) is a discipline at the intersection of computer science (algorithms), mathematics, and management. The purpose of OR is to propose scientific methods for solving practical optimization problems in large-scale systems (industrial, government, organizations, etc.); see, for example, the white paper on Operational Research, which describes applications such as optimizing energy distribution at EDF or flight crew scheduling at Air France. OR is a key discipline in many industries, and the impact of its practical applications in the academic world is evident, for example, in recent remarks by Cédric Villani (Fields Medalist) on France Inter or in the daily newspaper Le Monde, which mention OR, or in the recent Nobel Prize in Economics (October 2012) regarding coupling problems in markets where standard models do not work.

The current bottlenecks in RO lie in so-called hard problems (in complexity theory) and large-scale problems. The challenge is to significantly reduce the computation time required to solve these problems. For example, the recent Roadef challenge organized by Google (involving more than 80 international teams) required solving several fundamental combinatorial optimization problems, such as bin packing. Historically, research on these problems has focused on developing more efficient algorithms. The challenge today, with the ubiquity of multi-core machines and the low-cost availability of accelerators, is to leverage these new resources to push the boundaries of solving these problems.

At first glance, the use of parallel architectures has been well understood for many years: on the one hand, there is a substantial body of parallel algorithms; on the other hand, for the key challenges of synchronization between concurrent entities and the scheduling of activities (tasks) on computing resources, there are heuristic approaches that are generally effective in practice. Nevertheless, there remain hard problems to solve stemming from hardware complexity. Indeed, modern parallel architectures—whether multi-core or accelerator-based—feature a complex memory hierarchy (L1, L2, L3 caches, memory banks, etc.). Effective utilization therefore remains beyond the scope of the approaches mentioned. Solutions to this problem involve simplifying the architecture (at the cost of a trade-off between simplicity and performance) and must be addressed along three main lines: 

1. Designing algorithms that take memory access constraints into account;
2. Use of a high-level programming model;
3. Use of new scheduling techniques that take into account the location of data across different physical memory locations.

The MOAIS team has expertise in these three areas and, more specifically, is developing an execution framework that, when combined with tailored scheduling algorithms, makes it possible to easily define a large set of fine-grained tasks with dependencies, which will be executed on a heterogeneous architecture (multi-CPU, multi-GPU).

Research on parallel algorithms for advanced generic optimization methods has been ongoing for many years (see, for example, Bertrand Le Cun’s work on the parallel Branch and Bound algorithm). Our aim is to focus on the building blocks of operations research in order to develop accelerated methods for these fundamental components, which frequently appear in optimization problems.

The first problem we will examine is the knapsack problem: given a set of items, each with a volume and a profit, we seek to select a subset of these items to place in a knapsack of finite volume in order to maximize the profit of the resulting knapsack. This knapsack problem is “difficult” but fundamental in operations research (OR), particularly because it appears as a subproblem in many applications—for example, when managing a time budget in production or a monetary budget for portfolio construction. One of the basic solution techniques is formulation as an integer linear programming problem and the use of solvers to solve the problem. During the solution process, many knapsack problems must be solved very quickly and exactly. There are numerous techniques for efficiently solving this problem for problems of limited size, and advances in many applications will depend on accelerating these solution techniques, particularly through parallelization on processors and accelerators. In 2012, Boyer, El Baz, and Elkihel initiated work on this problem using a graphics card as an accelerator. We will continue this work by generalizing the problem and employing hybrid programming and the simultaneous use of multiple accelerators.

Another key problem in this project is bin packing: the goal is to place objects into the fewest possible containers. Each object and each container has a given volume. This problem has a wide range of applications, such as scheduling tasks on machines or creating class schedules. In the latter example, the objects can be classes and the containers can be classrooms. Resource allocation problems (time, money, energy, water, etc.) or logistics problems often involve bin packing as a subproblem.

We will consider these basic problems and their extensions, particularly in the context of compact data: An instance of a classic combinatorial optimization problem consists of a list of n objects, each with a list of attributes. In this case, the encoding of an instance can be done in O(n L), where L is the size of the encoding of the largest attribute. However, it is often the case that an instance can be encoded more compactly, for example, when the objects can be aggregated into a small number of distinct types. When this is the case, it suffices to describe the attributes of a single representative object per type and to specify the number of objects of each type. When the data is encoded in this way, it is a high-multiplicity (HM) problem. In this case, the complete description of a solution for each of the n objects is only pseudo-polynomial in the size of the instance. For this type of problem, even proving NP-completeness can be difficult. This type of situation is encountered in repetitive manufacturing environments or in applications where the number of objects is reduced by aggregating different objects with similar characteristics. The resulting problem is only an approximation of the original problem but may prove easier to solve. These problems are highly structured: Significant performance gains can be expected by using parallel algorithms. They currently present a major practical and theoretical challenge for the field.

We therefore aim to evaluate the benefits of using one or more accelerators to solve these problems and push the boundaries (in terms of reasonable computation time and problem size) within the constraints of current accelerators. We cannot directly adapt the most efficient sequential algorithms for these problems due to the technological constraints of the accelerators. The challenge is to develop new algorithms dedicated to parallelization for these problems; for example, combining divide-and-conquer and dynamic programming methods for hybrid parallel systems.

The project's objectives are

• Have a library of accelerated fundamental algorithms for the building blocks of RO.
• Develop strong expertise in this field at the national level,
• Strengthen international partnerships and raise awareness in this area
• And, of course, to produce original research findings that will be presented at conferences and published in articles.

Partnerships

This project brings together complementary teams from the Grenoble site. The ROSP (Operations Research for Production Systems) team at the G-SCOP laboratory contributes expertise in combinatorial optimization and operations research, as well as in practical problems and industrial challenges. The MOAIS team at LIG specializes in parallel algorithms, parallel programming, scheduling, and accelerators (many-core).

Participants

• Nadia Brauner (Professor, UGA),
• Van Dat Cung (Professor, Grenoble INP)
• Michael Gabay (Ph.D. student)
• Thierry Gautier (Senior Researcher at INRIA)
• Grégory Mounié (Ph.D. candidate, Grenoble INP)
• Rémi Piotaix (Intern)
• Brice Videau (Postdoc)

Bibliography

1. N. Brauner, S. Gravier, L.-P. Kronek, F. Meunie. LAD models, trees, and an analog of the fundamental theorem of arithmetic. *Discrete Applied Mathematics*. (Available online at https://doi.org/10.1016/j.dam.2012.12.004), 2012.
2. J. Darlay, N. Brauner, and J. Moncel. "Dense and Sparse Graph Partition." *Discrete Applied Math*, 160(16–17):2389–2396, 2012.
3. N. Brauner, G. Finke, V. Lehoux-Lebacque, C. Rapine, H. Kellerer, C. Potts, V. Strusevich. Operator Non-Availability Periods. 4OR: A Quarterly Journal of Operations Research, 7(3):239-253, 2009.
4. N. Brauner, G. Finke, V. Lehoux-Lebacque, C. Potts, and J. Whitehead. “Scheduling of Coupled Tasks and No-Wait Robotic Cells.” *Computers & Operations Research*, 36(2): 301–307, 2009.
5. F. Broquedis, T. Gautier, V. Danjean. libKOMP, an Efficient OpenMP Runtime System for Both Fork-Join and Data Flow Paradigms. IWOMP, pp. 102–115, Rome, Italy, June 2012.
6. T. Gautier, J.V. F. Lima, N. Maillard, B. Raffin. XKaapi: A Runtime System for Data-Flow Task Programming on Heterogeneous Architectures, IPDPS’2013, Boston, USA, 2013.
7. T. Gautier, J.V. F. Lima, N. Maillard, B. Raffin. Locality-Aware Work Stealing on Multi-CPU and Multi-GPU Architectures, 6th Workshop on Programmability Issues for Heterogeneous Multicores (MULTIPROG), HiPEAC, Berlin, Germany, 2013.
8. E. Hermann, B. Raffin, F. Faure, T. Gautier, J. Allard. Multi-GPU and multi-CPU parallelization for interactive physics simulations, EUROPAR 2010, Ischia, Naples, Italy, 2010.
9. J.V.F. Lima, T. Gautier, N. Maillard, V. Danjean. Exploiting Concurrent GPU Operations for Efficient Work Stealing on Multi-GPUs. 24th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Columbia University, New York, USA, October 2012.
10. J. Toss, T. Gautier. A New Programming Paradigm for GPGPU. EUROPAR 2012, Rhodes, Greece, August 2012.
11. C. Rapine, N. Brauner, G. Finke, V. Lebacque. Single Machine Scheduling with Small Operator-Non-Availability Periods, Journal of Scheduling, 15:127–139, 2012.