Hi, I was thinking about the following: A company has designed an algorithm in MATLAB. They decide on some hardware architecture on which the algorithm is going to be implemented. Now...the guy who programmed the algorithm in MATLAB didn't know anything about the hardware architecture but now he faces the problem of having to port the code and probably also modifying various functions in his algorithm such that it is optimal and suitable for implementation on the chosen hardware architecture. My question is: Are there any methods for how the algorithm is best optimized / adapted to the given architecture? I have heard about HW/SW codesign and read a little about it but it doesn't seem to applicable to the situation described above. Maybe there are some experts out there willing to enlighten me?
Question about re-designing an algorithm when hardware architecture is fixed
Started by ●April 11, 2006
Reply by ●April 11, 20062006-04-11
Reply by ●April 11, 20062006-04-11
John wrote:> Hi, > > I was thinking about the following: > > A company has designed an algorithm in MATLAB. They decide on some > hardware architecture on which the algorithm is going to be implemented. > Now...the guy who programmed the algorithm in MATLAB didn't know anything > about the hardware architecture but now he faces the problem of having to > > port the code and probably also modifying various functions in his algorithm > such that it is optimal and suitable for implementation on the chosen > hardware architecture. > > My question is: Are there any methods for how the algorithm is best > optimized / adapted to the given architecture? > > I have heard about HW/SW codesign and read a little about it but it doesn't > seem to applicable to the situation described above. > > Maybe there are some experts out there willing to enlighten me?An algorithm is independent of the hardware it's implemented on and the language it's expressed in. Code can be optimized for particular hardware, and hardware can be designed to allow more efficient implementation of particular code. (Zero-overhead loops and single-cycle MACs come to mind.) Your question isn't trivial, even though that response is. I'm sure you mean something, but I don't know what. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 12, 20062006-04-12
Jerry Avins wrote:> John wrote: > >> Hi, >> >> I was thinking about the following: >> >> A company has designed an algorithm in MATLAB. They decide on some >> hardware architecture on which the algorithm is going to be implemented. >> Now...the guy who programmed the algorithm in MATLAB didn't know anything >> about the hardware architecture but now he faces the problem of having to >> port the code and probably also modifying various functions in his >> algorithm >> such that it is optimal and suitable for implementation on the chosen >> hardware architecture. >> >> My question is: Are there any methods for how the algorithm is best >> optimized / adapted to the given architecture? >> >> I have heard about HW/SW codesign and read a little about it but it >> doesn't >> seem to applicable to the situation described above. >> >> Maybe there are some experts out there willing to enlighten me? > > > An algorithm is independent of the hardware it's implemented on and the > language it's expressed in. Code can be optimized for particular > hardware, and hardware can be designed to allow more efficient > implementation of particular code. (Zero-overhead loops and single-cycle > MACs come to mind.) > > Your question isn't trivial, even though that response is. I'm sure you > mean something, but I don't know what. > > JerryYabbut. An algorithm is, indeed independent of the hardware it's implemented on, etc., but two algorithms with identical results can have widely different execution speeds and/or memory requirements, particularly when machine architecture is taken into account. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Posting from Google? See http://cfaj.freeshell.org/google/
Reply by ●April 12, 20062006-04-12
John wrote:> Hi, > > I was thinking about the following: > > A company has designed an algorithm in MATLAB. They decide on some > hardware architecture on which the algorithm is going to be implemented. > Now...the guy who programmed the algorithm in MATLAB didn't know anything > about the hardware architecture but now he faces the problem of having to > port > the code and probably also modifying various functions in his algorithm such > that > it is optimal and suitable for implementation on the chosen hardware > architecture. > > My question is: Are there any methods for how the algorithm is best > optimized / adapted > to the given architecture? > > I have heard about HW/SW codesign and read a little about it but it doesn't > seem to applicable to the situation described above. > > Maybe there are some experts out there willing to enlighten me? > > >AFAIK it's like solving differential equations: You guess a solution, then you backfill to prove it or disprove it. Assuming that we can take 'algorithm' in the wider sense of 'get this job done in this general way' then yes, there is often a great deal of room for optimizing it to a particular processor. Unfortunately, I don't know of any really systematic way other than applying some heuristics for each given processor type (i.e. fixed point is way cheaper than floating on many processors, vector operations are far cheaper on DSPs, etc.). -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Posting from Google? See http://cfaj.freeshell.org/google/
Reply by ●April 12, 20062006-04-12
Jerry Avins wrote:> John wrote: > > ... > > My question is: Are there any methods for how the algorithm is best > > optimized / adapted to the given architecture?when the algorithm is designed from top-down, you should probably have a good feel for what operations are the most numerically intensive. often these will be in the inner-most loops and could be a "dot product" type of summation or a power series or something like that. this is where to do a little "bottom-up" design and that will have some dependancy on the device doing it. other things to deal with is knowing what the hardware architecture is really good at. does it move numbers really fast but is slow at multiplication? that will affect things. as Jerry sez: " Engineering is the art of making what you want from things you can get." if what you are stuck with is some 8051 or PIC like moron of a processor, you'll likely want to minimize the number of multiplications to do. and certainly the divisions. in other contexts, likely with a real DSP, you can multiply and add numbers as fast as you can move them. also, the word width, fixed or floating point, width of the "accumulator", could have an effect on how an algorithm is best optimized and ported from MATLAB. MATLAB is good for analyzing data and for testing proof-of-concept, but they use double-precision numbers and your target might not. ...> An algorithm is independent of the hardware it's implemented on and the > language it's expressed in. Code can be optimized for particular > hardware, and hardware can be designed to allow more efficient > implementation of particular code. (Zero-overhead loops and single-cycle > MACs come to mind.)while i agree with what i think you mean, Jerry, i might say it differently. the *philosophy* or purpose or mathematical end of an algorithm might well be independent of the hardware it's implemented on or language it's expressed in, but the *algorithm*, the *method* might very well be different. and it isn't just a difference in expression due to differences in language. an example, Horner's method of evaluating a polynomial: http://math.fullerton.edu/mathews/n2003/HornerMod.html p(x) = a[0] + x*(a[1] + ... + x*(a[N-2] + x*(a[N-1] + x*a[N]))...) makes the best sense when doing it by hand (or with a calculator by hand) or with a general purpose CPU in a "high level" language, but is not the efficient way to do it in a DSP like the 56K because the moves cost as much as the multiplies. an even better example of the difference is the "naive DFT" vs. the FFT. or even different ways of doing the FFT, such as Decimation-in-Time vs. Decimation-in-Frequency or Winograd or Hartley Fourier Transforms. these are all *different* algorithms, not just different code optimizations, yet they do or are meant to do the same thing. another one: fast-convolution vs. straight forward FIR filter summation. different algorithms with the same purpose. but if your memory is limited or if you want the least possible quantization error, fast-convolution might not be best and that component of a larger system could be changed as it migrates from MATLAB to a target DSP. r b-j
Reply by ●April 12, 20062006-04-12
On Wed, 12 Apr 2006 04:23:40 +0200, "John" <john@nospam.com> wrote:>A company has designed an algorithm in MATLAB. They decide on some >hardware architecture on which the algorithm is going to be implemented. >Now...the guy who programmed the algorithm in MATLAB didn't know anything >about the hardware architecture but now he faces the problem of having to port >the code and probably also modifying various functions in his algorithm such that >it is optimal and suitable for implementation on the chosen hardware architecture. > >My question is: Are there any methods for how the algorithm is best >optimized / adapted to the given architecture? >Yes and they are good sense, and hard work. The idea is that any algorithm can be implemented in any Von Neuman machine so the only criteria is whether you can meet the performance requirements of the algorithm with the hardware you have. This is certainly a task which can be accomplished by the original programmer. If there is a C compiler,even if it's not a very good one, it makes sense to convert the matlab code to C and see what you get. If not, one has to start analyzing the hardware ISA and see how the code can be mapped to it. After that it's an iterative effort to convert,debug and performance analysis. When you meet the performance requirements you can stop but there is still the option of continuing a bit for power consumption. If the hardware ISA is fixed point, converting the matlab code to fixed point C would really help a lot. Of course it depends what the hardware ISA looks like too. If it's a nice orthogonal ISA with several registers the task is much easier. One can even port a C compiler to start with (lcc is a good place to look). If it's a VLIW type architecture, more head scratching maybe necessary to come up with a satisfactory result.
Reply by ●April 12, 20062006-04-12
Not sure if this help. You want to see this http://www.mathworks.com/products/tic6000/ Matlab can generate codes for DSP target. You have to check the toolbox for actually way to use it though.
Reply by ●April 12, 20062006-04-12
John wrote:> A company has designed an algorithm in MATLAB. They decide on some > hardware architecture on which the algorithm is going to be implemented. > Now...the guy who programmed the algorithm in MATLAB didn't know anything > about the hardware architecture but now he faces the problem of having to > port > the code and probably also modifying various functions in his algorithm such > that > it is optimal and suitable for implementation on the chosen hardware > architecture. > > My question is: Are there any methods for how the algorithm is best > optimized / adapted > to the given architecture?If the hardware is made up of DSP(s), then an obvious choice for optimization is to use the vendor library functions for standard routines like FFT / IIR / FIR , etc. They are likely to be coded close to optimal, and chances are high that the number crunching core of the algorithm can be covered using library routines. Regards, Andor
Reply by ●April 12, 20062006-04-12
Tim Wescott wrote:> Jerry Avins wrote: > >> John wrote: >> >>> Hi, >>> >>> I was thinking about the following: >>> >>> A company has designed an algorithm in MATLAB. They decide on some >>> hardware architecture on which the algorithm is going to be implemented. >>> Now...the guy who programmed the algorithm in MATLAB didn't know >>> anything >>> about the hardware architecture but now he faces the problem of >>> having to >>> port the code and probably also modifying various functions in his >>> algorithm >>> such that it is optimal and suitable for implementation on the chosen >>> hardware architecture. >>> >>> My question is: Are there any methods for how the algorithm is best >>> optimized / adapted to the given architecture? >>> >>> I have heard about HW/SW codesign and read a little about it but it >>> doesn't >>> seem to applicable to the situation described above. >>> >>> Maybe there are some experts out there willing to enlighten me? >> >> >> >> An algorithm is independent of the hardware it's implemented on and >> the language it's expressed in. Code can be optimized for particular >> hardware, and hardware can be designed to allow more efficient >> implementation of particular code. (Zero-overhead loops and >> single-cycle MACs come to mind.) >> >> Your question isn't trivial, even though that response is. I'm sure >> you mean something, but I don't know what. >> >> Jerry > > > Yabbut. > > An algorithm is, indeed independent of the hardware it's implemented on, > etc., but two algorithms with identical results can have widely > different execution speeds and/or memory requirements, particularly when > machine architecture is taken into account.Right, of course. The question states that the algorithm was originally implemented in Matlab. Be that as it may, once developed, it is what it is and can be written in any language in a way most suited to that language. The question also states that special hardware is developed to efficiently implement the algorithm. Surely, the development process is iterative, with a number of "what if it's done this way?" cycles, and a choice -- within some constraints -- of the best way. By the time the hardware is etched in silicon, the particular implementation is pretty well implied; co-design and all that. So it comes down to my not understanding the question in the context given. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
