1. INTRODUCTION

The paper consists in two main parts. The first one is the MPEI and CAD Centre presentation and analysis of previous experiences of MPEI teams in joint projects (Sections 1, 2). The second one describes the certain proposals for co-operation in the area of system-level design and especially the HW/SW codesign multimodel approach (Section 3).

MPEI is a training, research and commercial centre on power engineering, electrical engineering and electronics. The status of MPEI as a Technical University is characterized by the ties with foreign Universities of more than 22 countries, setting up of joint research centres and joint ventures. The main sources of the MPEI financing are provided for by federal budgeting system and payments coming from research programmes ordered by industries (figure 1, see the next page). The number of contracts signed in 1995 is 21 with the amount equal 525.000 USD excluding VAT (in 1991 the total contract sum was only 26.300 USD).

Having accepted a multilevel system of education MPEI has been offering 2 levels of technical education since 1992:

• Basic higher education (it leads to a diploma and a Bachelor's degree);
• Specialized higher education (it leads either to an engineer's diploma after 5,5 years or a Master's degree after 6 years).

Having received an engineer's diploma or a Master's degree the MPEI students can improve their qualifications through postgraduate courses leading to a Candidate (Ph.D.) and further a Doctor's (Dr.Sc.) degree. The MPEI postgraduate courses have distinguished themselves among similar courses in Russia through their programmes aimed at training highly-qualified specialists in 44 scientific branches (from Differential Equations, Radar Systems and Radio Navigation to Solid State Electronics&Microelectronics, CAD, Mathematical Methods and SW for Computer Systems&Networks etc.).

The precollege training complex includes 3 Lyceums and more than 10 secondary schools with specilized classes which offers advanced programmes in mathematics, physics and computer science.

MPEI communications infrastructure allows interconnecting facilities in Internet and another global networks such as FREENet, Relcom (RELARN International Project), Runnet via terrestrial and satellite links. VSAT satellite links are provided by the station "SLAVYANKA" developed by the MPEI pilot design centre for the Open European Technical University and ordered by UNESCO and UNIDO ("SLAVYANKA" stations will be installed in Paris and Vienna in 1996-97).

The longterm goal of CAD Centre founded in 1988 at the Dept. of Computer Engineering of MPEI is to develop EDA tools for different applications. The Centre has 12 staff members including 1 Dr.Sc., 4 Ph.D. and 7 softengineers.

The previous experience is defined by HW/SW codesign of real-time embedded systems in avionics and autoelectronics. Generalized Structure Synthesis System (GSSS) was presented at the EURO-DAC'94 exhibition. Reseach activities are supported by professional software: Vantage, Xilinx, Synopsys, ViewLogic.

2. WHY PAN-EUROPEAN CO-OPERATION?

2.1. Recent history and objective difficulties

The status of science and education in Russia after the break-up of the Soviet Union changed for the worse. Till 1992 the USSR Academy of Science and the State Committee for Science and Technology supervised the fundamental research. Impetuous transition from such concerted "planning" to market economy created serious problems for universities and research centres. Being one of the leading research centre in Russia MPEI carries out research following national scientific programmes as well as research programmes of the RF Ministry of Science and the RF State Committee on Higher Education.

They can be devided into several major groups:

• State Programmes (e.g. "Promising Information Technologies", "Informatization of Russia");
• National Economy projects and state orders of the RF Ministry of Science (e.g. "Information of State Control Bodies, Social and Production Structures");
• Interuniversities programmes (e.g. "Methods and Hardware to Provide Information Safety", "Universities of Russia").

In accordance with scientific and technical programmes "Universities of Russia" and "Conversion" MPEI is engaged in more than 30 science projects. However grant budgeting is very poor: an average amount for a grant is 1.000-2.000 USD per year.

The salaries the leading scientists receive are insignificant: 100-150 USD for Doctors and 70-100 USD for Candidates, per month. The complicated rules of the grant application bureaucracy make all efforts unjustifiable in many cases. Naturally EU programmes cannot replace national support for education and scientific research in Russia and other CEE countries but they are extremely important in the transition period.

2.2. Look at technology transfer problems

From middle 70'th Western Europe countries have accumulated the diverse experience of technology transfer interactions between universities, scientific and industrial centres. It is not a secret that former Soviet science as a whole was military-oriented. However, it is known that Russian science still remains on a high level in many branches. It is a great challenge to put university developments into industry when the links with industry are missing. Furthemore, in Russia scientists carried out research with accounting the technical aspects of the subjects. But marketing is the weakest place of the research process. There are many reasons of such situation and they are not specific only for Russia.

MPEI has experiences of joint projects with some partners in USA (Motorola), Western Europe (Siemens, Xilinx) and Asia (Samsung, Gold Star). As extremely effective and useful we consider our co-operation with Xilinx in respect of organising the training centre and the annual workshop on Xilinx tools together with SCAN Ltd. (Moscow). The main difficulties in the co-operation with industry partners are defined by their strongly oriented specific interests. Often university scientists do not consider the task of their results embeding into industry technology as a primary goal.

So, one of the first points for successful projects is high quality management.

Typical problems arise from inconsistent and incompatible conditions and rules for Russia which are normal for EU countries:

• poor understanding of sophisticated rules of EU bureaucracy;
• taxation, money transfers, as a whole poor bank services, and generic financial aspects (e.g. real contradictions in understanding "Full economic cost basis" and "Marginal cost basis" in COPERNICUS).

These problems were discussed with project leaders at MPEI, and their conclusions base on experiences of participation in COPERNICUS, INCO-COPERNICUS, TEMPUS projects in different branches (e.g. ENJOIN, PECO projects etc.).

At last, the third group of challenges is the most important in our opinion. That is abundance of developed CAD tools at MPEI based on PC and UNIX platforms. As mentioned above our partners from industry previously take care of special (non-global!) technological subjects. The unique possibility for us to present our CAD tools for industry and scientific communities is to be engaged in the EU framework programmes. Furthermore, EU Co-operation projects are oriented at existing standards. That includes possibilities to make tools for European and global markets.

3. BASIC CONCEPT OF MULTIMODEL APPROACH TO CODESIGN

In this section we introduce MPEI approach to codesign.

3.1. Relative works

Modern hardware-software codesign methodologies such as the "specify-explore-refine" [6] or the work bench one [19] demand a set of adequate interactive models. These approaches, if they are acceptable, allow automatic partitioning at different levels of granularity [3,4,7,17] as in COSYMA and VULCAN II. Manual partitioning in some rapid prototyping systems, such as SIERA [12], a priori limits design space. To avoid adjacent challenges in automatic partitioning (communication overheads [4,7], compiler effects [4], preliminary restrictions in regard to programming style in a system specification, e.g. the exception of dynamic structures [7] and operating system calls [8]), it is necessary to use relatively neutral constructs for an internal design representation.

It is not a trivial task to introduce closeness metrics [1,2,10] or their combinations [18] in partitioning with multistage clustering because this approach assumes knowledge of special properties of the HW/SW codesign space, as well as the binary-constraint search algorithm [17]. The latter is "hard"-oriented to the only metric optimization, and it implies a possibility to order influencing parameters by some manner so that the cost function to be monotonic.

Object-oriented functional specifications (OOFS) [20] and UNITY language [1,2] allow neutral constructs in the specification without preliminary biasing the implementation to HW or SW. But the common shortcoming of these and above methodologies is the absence of any mechanism in their internal representations to predict the results and to control the partitioning process considering adjacent challenges. Codesign methodologies with the process network [12] or the communicating sequential processes [13] do not possess such possibilities too.

3.2. Distinctive features

The main objective of the presented approach is to introduce a set of high-level models for the HW/SW codesign result prediction in the early stages of the partitioning accounting above mentioned adjacent effects. These are a generalized functional model (GFM) for design space exploration and mapping onto target architectures, a mixed (data and control) flow model (MFM), a metaoperator net (MN) and a reduced flow model (RFM) (figure 2, see the next page). (The Zurich approach, described in the recent work T. Blickle, J. Teich, L. Thiele, System-Level Synthesis Using Evolutionary Algorithms, TIK-Report No. 16, April 1996, realizes the architecture selection (allocation) too.)

The multimodel (MM) approach avoids apriority restrictions in system specifications and allows to control partitioning using a special metric. This metric is the implementation complexity of MN. The MM paradigm assumes a multistage transformation of an initial representation (a mixed flow model) into a semantic (operational) model, then into a metaoperator model with a relaxed semantics, and, finally, the transition to RFM. The introduced metric permits the comparison of different alternative implementations before the partitioning, the argument choice of possible candidates for moving to HW, the reduction of HW/SW design space, and then the partitioning with some optimization algorithms (simulated annealing [9,11], group migration etc.).

The fundamentally new feature of the MM paradigm is the possibility to estimate a least upper bound of the implementation complexity, and the latter is acceptable for a transparent interpretation in timing domain due to the operational semantics as the word of the operation history. The length of this word is the number of processor cycles for SW segment runs.

The asymptotic complexity of MN estimation algorithms is , where is the number of basic functional blocks at the requisite level of granularity. These algorithms are used combining specially developed tools [14,15,16] with their expansion - the BENCH system for profiling and estimating of C/C++ system descriptions.

3.3. Model interaction in codesign

To illustrate the principal idea of the complexity estimation figure 3,a (see the next page) shows a control and data flow graph (CDFG)-based representation of a SW fragment where dashed lines present control dependencies and uninterrupted lines denote data flows. Results of the process appropriated for the function values initiate processes .

If to permit the abstraction from real values of operands in processes on the analogy of the abstract interpretation in functional programming [5] and the start of any process if and only if the operands are acceptable, then it is obvious that the process may be initialized to three times. Figure 3,c shows a suitable graph presentation - MN, that is in substance the indeterminate programming flow model. The criterion of the implementation complexity for this model by a method is defined as a simple sum of complexities for the respective implementations of functional blocks and the branch in processes and : . For data-independent complexities of processes . The model implementation is a nonredundant one if and only if the number of operands involved by appropriate processes is of all possible operands' numbers under all possible evolution variants of processes subject to the input specification.

For the given model this is determined by the least common multiple of the numbers of the involved operands: . . The complexity of nonredundant realizations is . Node complexities in MN are interpreted as numbers of processor cycles for appropriate SW segment run in the prototyping system BENCH (see figure 2). Coefficients at ( in example for figure 3,c) are node sections denoted by . Therefore the complexity of MN with nodes in the implementation is defined as . Only such MN transformation in partitioning and scheduling (see figure 2) is possible which does not violate the constraint .

A set of object functions and a set of object predicates give the set termed as a functional space. It corresponds to the system functionality deduced from the input specification. The mixed flow model is a directed multigraph with two classes of vertices one-to-one mapping sets and two classes of edges for data and control flows, as shown in figure 4 (see the next page).

MFM supports manifold function blocks with complex data structures in the input system specification, but it does not allow directly to estimale the implementation complexity. The metaoperator net (figure 5, see the next page) is the homomorphous image of MFM with - and -vertices one-to-one mapping - and -vertices. Auxiliary - and -vertices are used, if it is necessity, to organize together with - and -vertices appropriate - and -nodes. Numbers in squares at appropriate edges (see figure 5) deduced from special marking procedure uniquely determine node sections (for more details, see [15]). RFM permits to define the problem of composing a candidate set for HW moving as a classical task of the critical path search (figure 6).

4. CONCLUSIONS

The CAD Centre of MPEI capabilities for co-operation and technology transfer in the framework of BENEFIT are presented in this paper. MPEI infrastructure permits to realize these possibilities in the proper way.

Inspite difficulties and unexpected problems we consider co-operation and technology transfer capabilities as helpful and the uniquely real way to realize MPEI scientific potential in the heavy transtion time for Russia. For MPEI Pan-European Co-operation is crucial for being still on a high level of science.

Necessary basic preconditions and criteria for successful co-operation in technology transfer are

1) the consistent partner's needs,

2) high quality project management,

3) understanding the European Union rules,

4) clear planning of goals and objectives in the initial stage of the project.

We hope that our R&D activity results could be useful for co-operation in the area of heterogeneous system design. The full report describing the Multimodel Approach to HW/SW Codesign will be available from http://cad.mpei.ac.ru/docs/groups/topvv.html.

REFERENCES

[1] E. Barros and W. Rosenstiel, A Method for Hardware/Software Partitioning, Compeuro, IEEE CS Press (1992) 580-585.

[2] E. Barros, W. Rosenstiel and X. Xiong, A Method for Partitioning UNITY Language in Hardware and Software, in: Proceedings EURO-DAC'94 with EURO-VHDL'94, Grenoble, France (1994) 220-225.

[3] T. Benner, R. Ernst and A. Osterling, Scalable Performance Scheduling for Hardware-Software Cosynthesis, in: Proceedings EURO-DAC'95 with EURO-VHDL'95, Brighton, UK (1995) 164-169.

[4] R. Ernst, J. Henkel and T. Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test of Computers (Dec. 1993) 64-75.

[5] A.J. Field and P.G. Harrison, Functional Programming (Addison-Wesley, 1988).

[6] D.D. Gajski and F. Vahid, Specification and Design of Embedded Hardware-Software Systems, IEEE Design & Test of Computers (Spring 1995) 53-67.

[7] R.K. Gupta and De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test of Computers (Sept. 1993) 29-41.

[8] R.W. Hartenstein et al, A Two-Level Hardware/Software Co-Design Framework for Automatic Accelerator Generation, in: Proceedings Design Methodologies for Microelectronics, Smolenice-Vienna (1995) 145-152.

[9] S. Kirkpatrick, C. Gelatt, Jr. and M. Vecchi, Optimization by Simulated Annealing, Science 220 (1983) 671-680.

[10] E.D. Lagnese and D.E. Thomas, Architectural Partitioning for System Level Synthesis of Integrated Circuits, IEEE Trans. on CAD 10 (7) (1994) 847-860.

[11] P. Roussel-Ragot and G. Dreyfus, A Problem Independent Parallel Implementation of Simulated Annealing: Models and Experiments, IEEE Trans. on CAD 9 (8) (1990) 827-835.

[12] M.B. Srisvastava and R.W. Brodersen, SIERA: A Unifed Framework for Rapid-Prototyping of System-Level Hardware and Software, IEEE Trans. on CAD of IC and Systems 14 (6) (1995) 676-693.

[13] D.E. Thomas, J.K. Adams and H. Schmit, A Model and Methodology for Hardware-Software Codesign, IEEE Design & Test of Computers (Sept. 1993) 6-15.

[14] V.V. Toporkov, Hardware-Software Cosynthesis by Metaoperator Net, in: Proceedings VHDL-Forum for CAD in Europe, Fall'94 Meeting at EURO-DAC'94 with EURO-VHDL'94, Grenoble, France (1994) 17-27.

[15] V.V. Toporkov, An Adaptive Strategy in Hardware-Software Codesign for Real-Time Embedded Systems, in: Proceedings Design Methodologies for Microelectronics, Smolenice-Vienna (1995) 187-194.

[16] V.V. Toporkov, Performance-Complexity Analysis in Hardware-Software Codesign for Real-Time Systems, in: Proceedings EURO-DAC'95 with EURO-VHDL'95, Brighton, UK (1995) 340-345.

[17] F. Vahid, J. Gong and D.D. Gajski, A Binary-Constraint Search Algorithm for Minimizing Hardware during Hardware/Software Partitioning, in: Proceedings EURO-DAC'94 with EURO-VHDL'94, Grenoble, France (1994) 214-219.

[18] F. Vahid and D.D. Gajski, Closeness Metrics for System-Level Functional Partitioning, in: Proceedings EURO-DAC'95 with EURO-VHDL'95, Brighton, UK (1995) 328-333.

[19] J. Wilberg, R. Camposano and W. Rosenstiel, Design Flow for Hardware/Software Cosynthesis of a Video Compression System, in: Proceedings 3rd Int. Workshop on Hardware/Software Codesign, Grenoble, France (1994) 73-80.

[20] N.S. Woo, A.E. Dunlop and W. Wolf, Codesign from Cospecification, IEEE Computer (Jan. 1994) 42-47.

BENEFIT Special Report Main Page