Mail Archives: djgpp/1999/04/22/12:50:31.1
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
|
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.
- Raw text -