From: "Ya'qub" <rick AT nct-active DOT com>
Newsgroups: comp.os.msdos.djgpp
Subject: Fw: DSP Heap Manager Algorithm
Date: Wed, 21 Apr 1999 18:22:11 +0100
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.00.2014.211
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2014.211
NNTP-Posting-Host: 193.123.236.199
Message-ID: <371e08c1.0@nnrp1.news.uk.psi.net>
X-Trace: 21 Apr 1999 18:20:01 GMT, 193.123.236.199
Lines: 65
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Greetings,
    I found this on the comp.dsp newsgroup and thought that maybe this would
be of interest to members of this newsgroup. I haven't got a clue what it's
about but it sounds like something programmers might like to know.
Regards
Ya'qub

----- Original Message -----
From: Gary Cameron <garyc AT istar DOT ca>
Newsgroups: comp.arch.embedded,comp.dsp
Sent: 21 April 1999 04:39
Subject: DSP Heap Manager Algorithm


>     I have just written a heap manager for the 563xx DSP as part of a
> graduate course I just finished.  It supports modulus or linear address
> bound heap memory allocation in any memory space, (X, Y, L, or P) and uses
a
> rather unique algorithm for keeping track of free memory blocks, which is
> much faster, and less prone to fragmentation than the traditional linked
> list method in K & R.  The algorithm can be ported to other DSPs which
need
> modulus aligned memory as well.  Nothing is wasted - the unaligned portion
> above and below any 2^n modulus aligned blocks can be allocated to smaller
> modulus blocks, or linear memory.  The (de)allocation time is linear with
> respect to the number of currently allocated blocks, and can be bounded to
a
> fixed upper limit, simply by placing a hard limit on the total number of
> allocated blocks.  The free block search loop uses only four CPU
> instructions.  Although the source is particular to the 563xx, the
algorithm
> should work well with any number of DSPs, so it may be a candidate for the
> DSP tricks web page, if you don't find any flaws in it, and think it is a
> worthwhile contribution.
>
> I haven't done much research in the area, but I think the block allocation
> strategy is rather unique.  Aside from reducing fragmentation, it is not
as
> prone to page swapping, since the block list is only stored in one place,
> which is separate from the heap memory being allocated or freed.  I
suspect
> it might find use in more general purpose CPUs as well.
>
>     I do not have a web page, (Item #6711 on my to do list) but you can
> email me back at garyc AT istar DOT ca if you want a copy of the .zip file
> containing the source and documentation.  I am publishing both the source
> and the algorithm as open source freeware under GPL terms.  I have bounced
> the idea off a number of people at the office, and they do not see any
flaws
> in the design.  The code seems to work properly with the test application
I
> have written, and I would like to now throw the idea open to "the world"
for
> further testing, comments and feedback.  I have received a number of
useful
> and interesting suggestions from other DSP developers which I plan to
> incorporate in a later revision.  The details of the algorithm are
sketched
> in the readme.txt file within the .zip file - I would like to have
included
> it here, but it is rather lengthy, and some people might not appreciate
such
> a long posting.