Dear Engin,
I understand the network overhead and we can make that into an explicit
command, and not the default functionality of the structure. Also we can
call it something other than lists, for example OpList (short for
Optimizable List). However, the user will not have any power to control
which data structure the OpList gets converted to, i.e. It depends on the
usage characteristics of that specific function. My aim here is to minimize
complexity during normal usage with a little storage overhead, storing
usage trends as metadata in the form of instance variables.
The developer or user can also call a status function which suggests wether
running the optimization function is advisable or not.
So what I am saying can be understood like this (using code representation
not actual code)
class OpList
{
int w1, w2, w3, x1, x2, y, z1, z2 // variables which store usage
trends (ultimately forming parameters for a deterministic equation)
void optimize()
{
// some computation based on w1, w2, w3, x1, x2, y, z1, z2
}
void status()
{
if ( some condition )
print ( " Optimization necessary " )
else if (some condition )
print ( " Optimization suggested but not necessary ")
else
print ( " Optimization not required " )
}
}
Please do let me know if I am thinking in the right direction or even if
it's an unnecessary addition.
Thanks and Regards,
Raghav Arora
On Mon, Mar 13, 2017 at 9:48 PM, Engin Kayraklioglu <[email protected]>
wrote:
> Hello,
>
> First of all we have a rather simple, non-distributed, non-parallel-safe
> list structure in Chapel:
>
> http://chapel.cray.com/docs/latest/modules/standard/List.html
>
> Structures you suggested seems a good list for common structures.
>
> As for optimizations: I like the general idea. I can imagine
> asynchronous tasks coming to help create some redundancy/variation in
> the way the data is stored. But at the same time, I'd be very careful
> since such reorganizations could create a lot of communication over the
> network. Especially if we are thinking about doing such operations
> without any instructions from the programmer, it can create unexpected
> performance overheads.
>
> Engin
>
> On 03/13/2017 04:29 PM, Raghav Arora wrote:
> > Hello Engin and Param,
> >
> > As Engin already knows, I have shown interest in developing distributed
> > data structures.
> >
> > I think we should start with basic data structures like:
> >
> > 1. Stack
> > 2. Queue
> > a. Basic Queue
> > b. Priority Queue
> > c. Dequeue
> > d. Circular Queue
> > 4. Sets
> >
> >
> > Then we should implement linked lists - both single and double linked
> >
> > Then we can use these structures further to implement Trees and Graphs.
> >
> > What are your thoughts? Also, in case an implementation for any of these
> > already exists, please forgive me as I am new to Chapel.
> >
> > And I tried to think over what Engin said about different
> > implementations for different workloads, and I think we can have a
> > generic data type called List (or maybe anything else), which implements
> > functionality from different data structures depending on the conditions
> > during their initialization. Furthermore, we can also have an optimize
> > function which interchanges implementation between data structures by
> > converting the way the data is stored. For example, Let's say I am doing
> > a lot of search operations on an array. A better data structure to carry
> > out search operations is a binary search tree. We can easily detect
> > operations we do on these lists and increment / decrement certain
> > parameters in a function whose output decides which data structure to
> > continue with. Again, what are your thoughts?
> >
> >
> > Best,
> > Raghav
> >
> > On Mon, Mar 13, 2017 at 7:18 PM, Engin Kayraklioglu <[email protected]
> > <mailto:[email protected]>> wrote:
> >
> > Hey Param,
> >
> > I think the basic ones you listed are the most important ones.
> >
> > (If you want to consider hashtables, you should be aware of
> associative
> > domains/arrays in Chapel:
> > http://chapel.cray.com/docs/master/primers/primers/associative.html
> > <http://chapel.cray.com/docs/master/primers/primers/associative.html
> >)
> >
> > >From then on, if you want to expand, you can do it by adding more
> depth
> > or breadth to it. ie, you can propose to have small set of
> > performant/scalable distributed data structures (maybe by
> > proposing/investigating different queue implementations that can
> perform
> > differently under different workloads), or a bigger set of structures
> > that covers wider variety of functionality that you think would be
> > useful for Chapel.
> >
> > It depends on what you are able/want to do in the given time frame.
> >
> > Engin
> >
> > On 03/11/2017 11:35 AM, Param Hanji wrote:
> > > Hi Engin,
> > >
> > > I tried looking for existing distributed data structure libraries,
> and
> > > came across Hazelcast
> > >
> > <http://docs.hazelcast.org/docs/3.5/manual/html/
> distributed-data-structures.html
> > <http://docs.hazelcast.org/docs/3.5/manual/html/
> distributed-data-structures.html>>,
> > Multipol
> > >
> > <http://digitalassets.lib.berkeley.edu/techreports/ucb/
> text/CSD-95-879.pdf
> > <http://digitalassets.lib.berkeley.edu/techreports/ucb/
> text/CSD-95-879.pdf>>
> > and Ignite
> > > <https://ignite.apache.org/features/datastructures.html
> > <https://ignite.apache.org/features/datastructures.html>>, among
> others.
> > > I noticed that these libraries have implementations for different
> data
> > > structures and need insights about which data structures will be
> useful
> > > for Chapel users. I believe you or someone else who has used Chapel
> > > extensively, will be in a better position to identify data
> structures
> > > that are used often.
> > >
> > > Once we have figured out which structures are required, I can
> perhaps
> > > think about and propose implementations for them. I'm sure some
> basic
> > > ones like stack, queue, hashmap, set, etc. will be useful for most
> > > users. What others am I expected to include in the library?
> > >
> > > On Mon, Mar 6, 2017 at 10:57 PM Engin Kayraklioglu <
> [email protected] <mailto:[email protected]>
> > > <mailto:[email protected] <mailto:[email protected]>>> wrote:
> > >
> > > Hey Param,
> > >
> > > As far as distributed data structures, there is nothing
> > special that I
> > > can refer you to. I suggest searching what kind of distributed
> > data
> > > structure libraries out there (in other languages), and what is
> > > suitable/useful for Chapel.
> > >
> > > On a slightly related note:
> > >
> > > http://chapel.cray.com/docs/latest/modules/layoutdist.html
> > <http://chapel.cray.com/docs/latest/modules/layoutdist.html>
> > >
> > > Standard Distributions in this link discusses how Chapel
> > distributes
> > > arrays over multiple nodes in a system.
> > >
> > > Engin
> > >
> > > On 03/04/2017 07:59 AM, Param Hanji wrote:
> > > > Hi,
> > > >
> > > > I am Param Hanji, an undergrad student from India, studying
> > at the
> > > > National Institute of Technology, Karnataka. I came across
> > Chapel
> > > on the
> > > > GSoC '17 Organisations page and decided to give it a shot.
> > > >
> > > > I've downloaded Chapel on my laptop using Homebrew and
> > played around a
> > > > little to get used to the new language and am really liking
> the
> > > > experience. I followed some the tutorials mentioned on the
> > website.
> > > > After working with frameworks like OpenCL, CUDA, OpenMP
> > etc., using
> > > > Chapel for parallelising code seems so simplistic!
> > > >
> > > > I'd love to contribute to the existing codebase and am
> > interested
> > > in the
> > > > Distributed Data Structures project. This will require
> > creating an
> > > > entirely new module right? Are there any resources on
> > distributed data
> > > > structures that I can refer to?
> > > >
> > > > Cheers,
> > > > Param Hanji
> > > >
> > > >
> > > >
> > > >
> > > >
> > >
> > ------------------------------------------------------------
> ------------------
> > > > Check out the vibrant tech community on one of the world's
> most
> > > > engaging tech sites, SlashDot.org! http://sdm.link/slashdot
> > > >
> > > >
> > > >
> > > > _______________________________________________
> > > > Chapel-developers mailing list
> > > > [email protected]
> > <mailto:[email protected]>
> > > <mailto:[email protected]
> > <mailto:[email protected]>>
> > > > https://lists.sourceforge.net/lists/listinfo/chapel-
> developers
> > <https://lists.sourceforge.net/lists/listinfo/chapel-developers>
> > > >
> > >
> > > ------------------------------------------------------------
> ------------------
> > > Announcing the Oxford Dictionaries API! The API offers
> world-renowned
> > > dictionary content that is easy and intuitive to access. Sign
> up for an
> > > account today to start using our lexical data to power your
> apps and
> > > projects. Get started today and enter our developer
> competition.
> > > http://sdm.link/oxford
> > > _______________________________________________
> > > Chapel-developers mailing list
> > > [email protected]
> > <mailto:[email protected]>
> > > <mailto:[email protected]
> > <mailto:[email protected]>>
> > > https://lists.sourceforge.net/lists/listinfo/chapel-developers
> > <https://lists.sourceforge.net/lists/listinfo/chapel-developers>
> > >
> >
> > ------------------------------------------------------------
> ------------------
> > Check out the vibrant tech community on one of the world's most
> > engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> > _______________________________________________
> > Chapel-developers mailing list
> > [email protected]
> > <mailto:[email protected]>
> > https://lists.sourceforge.net/lists/listinfo/chapel-developers
> > <https://lists.sourceforge.net/lists/listinfo/chapel-developers>
> >
> >
>
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Chapel-developers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-developers
